# Journal of the ACM Bibliography

Mechthild Stoer and Frank Wagner. A simple min-cut
algorithm. Journal of the ACM, 44(4):585-591, July 1997.
[BibTeX entry]
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.

### Shortcuts: