A near-linear time algorithm for constructing a cactus representation of minimum cuts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A near-linear time algorithm for constructing a cactus representation of minimum cuts

Full text

Pdf (401 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 246-255

Year of Publication: 2009

Authors

David R. Karger	Massachusetts Institute of Technology, Cambridge, MA
Debmalya Panigrahi	Massachusetts Institute of Technology, Cambridge, MA

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 66, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We present an Õ(m) (near-linear) time Monte Carlo algorithm for constructing the cactus data structure, a useful representation of all the global minimum edge cuts of an undirected graph. Our algorithm represents a fundamental improvement over the best previous (quadratic time) algorithms: because there can be quadratically many min-cuts, our algorithm must avoid looking at all min-cuts during the construction, but nonetheless builds a data structure representing them all. Our result closes the gap between the (near-linear) time required to find a single min-cut and that for (implicitly) finding all the min-cuts.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Efim A. Dinitz, Alexander V. Karzanov, and Micael V. Lomonosov. On the structure of a family of minimum weighted cuts in a graph. In A. A. Fridman, editor, Studies in Discrete Optimization, pages 290--306. Nauka Publishers, Moscow, 1976.
	2	Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
	3	Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a directed graph, Journal of Algorithms, v.17 n.3, p.424-446, Nov. 1994
	4	David R. Karger, Minimum cuts in near-linear time, Journal of the ACM (JACM), v.47 n.1, p.46-76, Jan. 2000 [doi>10.1145/331605.331608]
	5	David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996 [doi>10.1145/234533.234534]
	6	Alexander V. Karzanov and E. A. Timofeev. Efficient algorithm for finding all minimal edge cuts of a non-oriented graph. Cybernetics, 22:156--162, 1986.
	7	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]
	8	Dalit Naor and Vijay V. Vazirani. Representing and enumerating edge connectivity cuts in RNC. In F. Dehne, J. R. Sack, and N. Santoro, editors, Proceedings of the 2^nd Workshop on Algorithms and Data Structures, volume 519 of Lecture Notes in Computer Science, pages 273--285. Springer-Verlag, August 1991.
	9	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]