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 条

[21] On computing minimum (s,t)-cuts in digraphs
Nagamochi, H
INFORMATION PROCESSING LETTERS, 2005, 93 (05) : 231 - 237
[22] Approximating minimum cost multigraphs of specified edge-connectivity under degree bounds
Fukunaga, Takuro
Nagamochi, Hiroshi
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2007, 50 (04) : 339 - 349
[23] Minimum Cuts in Directed Graphs via Partial Sparsification
Cen, Ruoxu
Li, Jason
Nanongkai, Danupon
Panigrahi, Debmalya
Saranurak, Thatchaphol
Quanrud, Kent
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, : 1147 - 1158
[24] I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
Bhushan, Alka
Sajith, G.
THEORETICAL COMPUTER SCIENCE, 2015, 575 : 33 - 41
[25] CORRIGENDUM TO "MINIMUM EDGE CUTS IN DIAMETER 2 GRAPHS"
Bickle, Allan
Schwenk, Allen
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023,
[26] On chromatic number and minimum cut
Alishahi, Meysam
Hajiabolhassan, Hossein
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 139 : 27 - 46
[27] MINIMUM CUTS AND SHORTEST CYCLES IN DIRECTED PLANAR. GRAPHS VIA NONCROSSING SHORTEST PATHS
Liang, Hung-Chun
Lu, Hsueh-I
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (01) : 454 - 476
[28] Parallel Minimum Cuts in O(m log2 n) Work and Low Depth
Anderson, Daniel
Blelloch, Guy E.
ACM TRANSACTIONS ON PARALLEL COMPUTING, 2023, 10 (04)
[29] Minimum s - t cut in undirected planar graphs when the source and the sink are close
Kaplan, Haim
Nussbaum, Yahav
28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 : 117 - 128
[30] Minimum Cuts of Simple Graphs in Almost Always Linear Time
Brinkmeier, Michael
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5431 : 226 - 237

← 1 2 3 4 5 →