Categories and Subject Descriptors: G.1.2 [Numerical Analysis]: Approximation -- graph algorithms
General Terms: Algorithms
Additional Key Words and Phrases: Min-Cut
Selected references
- Ravindra K. Ahuja, James B. Orlin, and Robert E. Tarjan. Improved time bounds for the maximum flow problem. SIAM Journal on Computing, 18(5):939-954, October 1989.
- Noga Alon. Generating pseudo-random permutations and maximum flow algorithms. Information Processing Letters, 35(4):201-204, 7 August 1990.
- Joseph Cheriyan, Torben Hagerup, and Kurt Mehlhorn. Can a maximum flow be computed on o(nm) time? In Michael S. Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, volume 443 of Lecture Notes in Computer Science, pages 235-248, Warwick University, England, 16-20 July 1990. Springer-Verlag.
- Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, July 1987.
- Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, October 1988.
- Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 165-174, Orlando, Florida, 27-29 January 1992.
- David R. Karger and Clifford Stein. An \tilde{O}(n^2) algorithm for minimum cuts. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 757-765, San Diego, California, 16-18 May 1993.
- David W. Matula. A linear time 2 + epsilon approximation algorithm for edge connectivity. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 500-504, Austin, Texas, 25-27 January 1993.
- Kurt Mehlhorn and Stefan Nä}her. LEDA: A platform for combinatorial and geometric computing. Communications of the ACM, 38(1):96-102, January 1995.
- Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583-596, 1992.
- Maurice Queyranne. A combinatorial algorithm for minimizing symmetric submodular functions. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 98-101, San Francisco, California, 22-24 January 1995.