Fully dynamic algorithms for edge connectivity problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully dynamic algorithms for edge connectivity problems

Full text

Pdf (1.24 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 317 - 327

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Zvi Galil	Columbia Univ., New York, NY
Giuseppe F. Italiano	Columbia Univ., New York, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 33, Citation Count: 5

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/103418.103454 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Giuseppe Di Battista , Roberto Tamassia, On-line graph algorithms with SPQR-trees, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.598-611, July 1990, Warwick University, England
	3	G. N. Frederickson, "Data structures for on-line updating of minimum spanning trees", SIAM J. Comput. 14 (1985), 781-798.
	4	H. Gabow, and R. E. Tarjan, "A linear-time algorithm for a special case of disjoint set union", J. Comput. Syst. Sc#. 30 (1985), 209-221.
	5	Z. Galil, and G. F. Italiano, "Fully dynamic algorithms for 2-edge connectivity", manuscript 1990.
	6	Z. Galfl, and G. F. Italiano, "Maintaining the 3-edgeconnected components of # graph on-fine', manuscript 1990.
	7	Z. Galfl, and G. F. It#liano, "Fully dynamic algorithms for 3-edge connectivity", in preparation.
	8	Zvi Galil , Giuseppe F. Italiano, Maintaining biconnected components of dynamic planar graphs (extended abstract), Proceedings of the 18th international colloquium on Automata, languages and programming, p.339-350, June 1991, Madrid, Spain
	9	F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
	10	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	11	J. Hopcroft, and R. E. Tarjan, "Dividing a graph into triconnected components", SIAM J. Comput. 2 (1973), 135-158.
	12	D. B. Johnson, "A priority queue in which initialization and queue operations take O(loglog D) time", Math. Syst. Th. 15 (1982), 295-309.
	13	K. Mehlhorn, Personal communication, 1990.
	14	John H. Reif, A topological approach to dynamic graph connectivity, Information Processing Letters, v.25 n.1, p.65-70, 20 April 1987 [doi>10.1016/0020-0190(87)90095-0]
	15	R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM J. Comput. 1 (1972), 146-160.
	16	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
	17	R. E. Tarjan, and U. Vishkin, "An efficient parallel biconnectivity algorithm". SIAM J_ Comlgut. 14 (1985), 862-864.
	18	J. Westbrook, and R. E. Tarjan, "Maintaining bridge-connected and biconnected components online", Tech. Rep. CS-T1#-228-89, Princeton University, August 1989. To appear in Algorithmica.

CITED BY 5

	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994
	Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.759-770, May 04-06, 1992, Victoria, British Columbia, Canada
	Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.495-506, May 04-06, 1992, Victoria, British Columbia, Canada
	G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States