A simple min-cut algorithm

ABSTRACT

We present an algorithm for finding the minimum cut of an undirected edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement, and has a surprisingly simple proof of correctness. Its runtime matches that of the fastest algorithm known. The runtime analysis is straightforward. In contrast to nearly all approaches so far, the algorithm uses no flow techniques. Roughly speaking, the algorithm consists of about |V| nearly identical phases each of which is a maximum adjacency search.

REFERENCES

• 1: R. K. Ahuja , J. B. Orlin , R. E. Tarjan, Improved time bounds for the maximum flow problem, SIAM Journal on Computing, v.18 n.5, p.939-954, Oct. 1989 [doi>10.1137/0218065]
• 2: N. Alon, Generating pseudo-random permutations and maximum flow algorithms, Information Processing Letters, v.35 n.4, p.201-204, Aug. 1990 [doi>10.1016/0020-0190(90)90024-R]
• 3: Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
• 4: FORD, L. R., AND FULKERSON, D. R. 1956. Maximal flow through a network. Can. J. Math. 8, 399-404.
• 5: FRANK, A. 1994. On the Edge-Connectivity Algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Universit6 J. Fourier, Grenoble, Switzerland.
• 6: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 7: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 8: Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a graph, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.165-174, September 1992, Orlando, Florida, United States
• 9: David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167281]
• 10: David W. Matula, A linear time 2 + &&egr; approximation algorithm for edge connectivity, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.500-504, January 25-27, 1993, Austin, Texas, United States
• 11: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
• 12: NAGAMOCHI, U., AND IBARAKI, T. 1992a. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 583-596.
• 13: Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
• 14: NISHIZEKI, T., AND POLJAK, S. 1989. Highly connected factors with a small number of edges. Preprint.
• 15: Maurice Queyranne, A combinatorial algorithm for minimizing symmetric submodular functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.98-101, January 22-24, 1995, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
min-cut