A GENERALIZATION OF THE MAXIMAL CLOSURE OF A DIGRAPH

被引:0
作者
MACHADO, AF
PERIN, C
机构
来源
IFIP TRANSACTIONS A-COMPUTER SCIENCE AND TECHNOLOGY | 1992年 / 12卷
关键词
NONNUMERICAL ALGORITHMS AND PROBLEMS; COMBINATORICS; GRAPH THEORY;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper studies the maximal closure problem and a generalization of this problem. A resolution of the first problem is proposed based on a transformation into a maximum, flow problem on a bipartite digraph, with overall complexity O(\V+\.(\V+\.\V-\+m)). Two iterative algorithms for the resolution of the second problem are presented. Each iteration involves the solution of a maximal closure problem. The first algorithm is theoretically simpler and its complexity is: O((SIGMA[u(i): i= 1,2..n]). \V+\.(\V+\.\V-\ +m)). The second one uses the scaling technique and has a complexity of: O(\V+\.(n.min(log2n,(log2C)1/2)+n.log2U.\V-\.\V+\+ m)). Where n is the number of vertices, m is the number of edges in the digraph, (V+,V-) is a bipartition of the set of vertices (V+={v(i):b(i) greater-than-or-equal-to 0} and V-={v(i):b(i) < 0}), C=max{c(ii):(v(i),v(j)) is-an-element-of E}, and U=max{d(ij):d(ij) is the length of the shortest directed path from v(i) is-an-element-of V+ to v(j) is-an-element-of max{u(i):i=1,2...n}.
引用
收藏
页码:395 / 401
页数:7
相关论文
共 50 条
  • [31] Statistical mechanics of maximal independent sets
    Dall'Asta, Luca
    Pin, Paolo
    Ramezanpour, Abolfazl
    PHYSICAL REVIEW E, 2009, 80 (06):
  • [32] On maximal entries in the principal eigenvector of graphs
    Papendieck, B
    Recht, P
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2000, 310 (1-3) : 129 - 138
  • [33] Characteristics of the maximal independent set ZDD
    David R. Morrison
    Edward C. Sewell
    Sheldon H. Jacobson
    Journal of Combinatorial Optimization, 2014, 28 : 121 - 139
  • [34] Evaluating Roadblocks to Implementing a Green Freight Transportation System: An Interval Valued Intuitionistic Fuzzy Digraph Matrix Approach
    Singh, Suneet
    Barve, Akhilesh
    Muduli, Kamalakanta
    Kumar, Anil
    Luthra, Sunil
    IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, 2024, 71 : 2758 - 2771
  • [35] A complete generalization of Gollnitz's "big" theorem
    Coelho, Terence
    Kim, Jongwon
    Russell, Matthew C.
    RAMANUJAN JOURNAL, 2021, 55 (01) : 73 - 102
  • [36] Generalized domination in closure systems
    Berry, A
    SanJuan, E
    Sigayret, A
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (07) : 1064 - 1084
  • [37] A Holistic Framework for Environment Conscious Based Material Selection and Experimental Assessment Using Digraph-Based Expert System
    Arularasan, A. N.
    Mathew, Manoj
    Sudhakar, M.
    Sivakumar, K.
    Perumal, S. Bhagavathi
    Madhu, P.
    Dhanalakshmi, C. Sowmya
    Lalvani, J. Isaac JoshuaRamesh
    SCIENTIFIC PROGRAMMING, 2022, 2022
  • [38] Decomposition of Smith graphs in maximal reflexive cacti
    Radosavljevic, Z.
    Mihailovic, B.
    Rasajski, A.
    DISCRETE MATHEMATICS, 2008, 308 (2-3) : 355 - 366
  • [39] On Maximal Energy of Trees with Fixed Weight Sequence
    Gong, Shicai
    Li, Xueliang
    Gutman, Ivan
    Xu, Guanghui
    Tang, Yuxiang
    Qin, Zhongmei
    Yang, Kang
    MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2016, 75 (02) : 267 - 278
  • [40] On a generalization of Nemhauser and Trotter's local optimization theorem
    Xiao, Mingyu
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 84 : 97 - 106