COUNTING THE NUMBER OF MINIMUM CUTS IN UNDIRECTED MULTIGRAPHS

被引：15
作者：
NAGAMOCHI, H [1 ]
SUN, Z [1 ]
IBARAKI, T [1 ]
机构：
[1] TOYOHASHI UNIV TECHNOL,DEPT INFORMAT & COMP SCI,TOYOHASHI 441,JAPAN
来源：
IEEE TRANSACTIONS ON RELIABILITY | 1991年 / 40卷 / 05期
关键词：
UNDIRECTED GRAPH; MULTIGRAPH; EDGE-CONNECTIVITY; MINIMUM CUT; POLYNOMIAL-TIME ALGORITHM; SPANNING FOREST; SPANNING SUBGRAPH; EDGE CONTRACTION; SUPER-LAMBDA;
D O I：
10.1109/24.106785
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The problem of counting the number of cuts with the minimum cardinality in an undirected multigraph arises in various applications such as testing the super-lambda-ness of a graph and calculating upper and lower bounds on the probabilistic connectedness of a stochastic graph G in which edges are subject to failure. This paper shows that the number \C(G)\ of cuts with the minimum cardinality lambda(G) in a multiple graph G = (V, E) can be computed in O(\E\ + lambda(G)\V\2 + lambda(G)\C(G) parallel-to V\) time.
引用
收藏
页码：610 / 614
页数：5
相关论文
共 49 条
12345