Augmenting undirected connectivity in RNC and in randomized Õ(n3) time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Augmenting undirected connectivity in RNC and in randomized Õ(n³) time

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 658 - 667

Year of Publication: 1994

ISBN:0-89791-663-8

Author

András A. Benczúr

Department of Mathematics, MIT, Cambridge MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195425 What is a DOI?

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	Cai, G-P. and Y-G. Sun, The minimum augmentation of any graph to a k-edge-connected graph, Networks, 19 (1989), pp. 151-172.
	2	Dinits, E.A., A.V. Karzanov and M.L. Lomonosov, On the structure of a family of minimal weighted cuts in a graph, Studies in Discrete Optimization (in Russian), A.A. Fridman (Ed), Nauka, Moscow (1976), pp. 290-306.
	3	András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
	4	Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
	5	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, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
	6	Gabow, H.N., Applications of a poset representation to edge connectivity and graph rigidity, Dept. ofComp. Sci., University of Colorado, Techn. Rept. CU-CS-545-91 (1991).
	7	Harold N. Gabow, Efficient splitting off algorithms for graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.696-705, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195436]
	8	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]
	9	Gomory, R.E. and T.C. Hu, Multi-terminal network flows. SIAM J. Appl. Math. 9 (1961), pp. 551-560.
	10	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
	11	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	12	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]
	13	Karzanov, A.V. and E.A. Timofeev, Efficient Algorithms for Finding all Minimal Edge Cuts of a Nonoriented Graph, Cybernetics 156-162, translated from Kibernetika 2 (1986), pp. 8-12.
	14	K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
	15	Naor, D., D. Gusfield, Ch. Martel, A fast algorithm for optimally increasing the edge connectivity, Proc. 31st Annual IEEE Symposium on Foundations of Comp. Sci. (1990), pp. 698-707.
	16	Naor, D. and V.V. Vazirani, Representing and enumerating edge connectivity cuts in RNC, Proc. Second Workshop on Algorithms and Data Structures (1991 ), Lecture Notes in Computer Science 519, Springer-Verlag, pp. 273-285.
	17	Toshimasa Watanabe , Akira Nakamura, Edge-connectivity augmentation problems, Journal of Computer and System Sciences, v.35 n.1, p.96-144, Aug. 1987 [doi>10.1016/0022-0000(87)90038-9]

CITED BY 6

	Hiroshi Nagamochi , Takashi Shiraki , Toshihide Ibaraki, Computing edge-connectivity augmentation function in Õ(nm) time, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.649-658, January 05-07, 1997, New Orleans, Louisiana, United States
	Yefim Dinitz , Zeev Nutov, A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.509-518, May 29-June 01, 1995, Las Vegas, Nevada, United States
	András A. Benczúr , David R. Karger, Augmenting undirected edge connectivity in Õ(n2) time, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.500-509, January 25-27, 1998, San Francisco, California, United States
	Hiroshi Nagamochi , Toshihide Ibaraki, Deterministic Õ(nm) time edge-splitting in undirected graphs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.64-73, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Hiroshi Nagamochi , Toshihide Ibaraki, Graph connectivity and its augmentation: applications of MA orderings, Discrete Applied Mathematics, v.123 n.1-3, p.447-472, 15 November 2002
	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