Counting the number of minimum cuts in undirected multigraphs

DOI10.1109/24.106785zbMath0739.90026OpenAlexW2102883744MaRDI QIDQ3987534

Toshihide Ibaraki, Hiroshi Nagamochi, Zheng Sun

Publication date: 28 June 1992

Published in: IEEE Transactions on Reliability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/24.106785

zbMATH Keywords

minimum cutpolynomial-time algorithmedge-connectivityspanning subgraphedge contractionspanning foreststochastic graphmultiple graphundirected multigraphnumber of cuts with minimum cardinality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Abstract computational complexity for mathematical programming problems (90C60) Reliability, availability, maintenance, inspection in operations research (90B25) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Canonical cactus representation for miminum cuts, Graphs with largest number of minimum cuts, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, Counting and sampling minimum cuts in genus \(g\) graphs, A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph, A linear time algorithm for computing 3-edge-connected components in a multigraph, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Integrating and Sampling Cuts in Bounded Treewidth Graphs