A simple min-cut algorithm
- 1 July 1997
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 44 (4), 585-591
- https://doi.org/10.1145/263867.263872
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 .Keywords
This publication has 9 references indexed in Scilit:
- Can a maximum flow be computed in o(nm) time?Published by Springer Science and Business Media LLC ,2005
- LEDA: a platform for combinatorial and geometric computingCommunications of the ACM, 1995
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992
- Generating pseudo-random permutations and maximum flow algorithmsInformation Processing Letters, 1990
- Improved Time Bounds for the Maximum Flow ProblemSIAM Journal on Computing, 1989
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956