Computing All Small Cuts in an Undirected Network
Authors:
- Hiroshi NagamochiHNHiroshi Nagamochi
- Kazuhiro NishimuraKNKazuhiro Nishimura
- Toshihide IbarakiTIToshihide Ibaraki
- 1 August 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 10 (3) , 469-481
Abstract
Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and n and m denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k < \four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.
Keywords
This publication has 9 references indexed in Scilit:
- On the number of small cuts in a graphInformation Processing Letters, 1996
- Efficient splitting off algorithms for graphs1994
- A simple min cut algorithm1994
- On a theorem of MaderDiscrete Mathematics, 1992
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992
- Augmenting Graphs to Meet Edge-Connectivity RequirementsSIAM Journal on Discrete Mathematics, 1992
- Suboptimal cuts: Their enumeration, weight and number1992
- A Reduction Method for Edge-Connectivity in Graphs1978
- The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐BondsNetworks, 1975