Improved data structures for fully dynamic biconnectivity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved data structures for fully dynamic biconnectivity

Full text

Pdf (1.28 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: 686 - 695

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Monika Rauch

Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 19, Citation Count: 11

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.195434 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	David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook, Maintenance of a minimum spanning forest in a dynamic plane graph, Journal of Algorithms, v.13 n.1, p.33-54, March 1992 [doi>10.1016/0196-6774(92)90004-V]
	2	D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig, "Sparsification- A technique for speeding up dynamic graph algorithms" Proc. 33nd Annual Syrup. on Foun. dations of Computer Science, 1992, 60-69.
	3	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification for dynamic planar graph algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.208-217, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167159]
	4	G. N. Frederickson, "Data Structures for On-line Updating of Minimum Spanning Trees" SIAM J. Comput. 14 (1985), 781-798.
	5	Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
	6	M. L. Fredman, private communication.
	7	M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
	8	John Hershberger , Monika Rauch , Subhash Suri, Fully Dynamic 2-Edge-Connectivity in Planar Graphs, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.233-244, July 08-10, 1992
	9	R. Johnson, D. Pearson, and K. Pingali, "Finding Regions Fast: Single Entry Single Exit and Control Regions in Linear Time." To appear in Proc. Sigplan'94 PLDL
	10	M. H. Rauch, "Fully Dynamic Biconnectivity in Graphs." Proc. 33nd Annual Syrup. on Foundations of Computer Science, 1992, 50-59.
	11	P. van Emde Boas, "Preserving order in a forest in less than logarithmic time and linear space", in.form. Process. Left., 6(3), 1977, 80-82.
	12	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

CITED BY 11

	David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.192-201, January 28-30, 1996, Atlanta, Georgia, United States
	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States
	R. Ravi , David P. Williamson, An approximation algorithm for minimum-cost vertex-connectivity problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.332-341, January 22-24, 1995, San Francisco, California, United States
	Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing with applications, Journal of the ACM (JACM), v.46 n.1, p.28-91, Jan. 1999
	Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Giuseppe Amato , Giuseppe Cattaneo , Giuseppe F. Italiano, Experimental analysis of dynamic minimum spanning tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.314-323, January 05-07, 1997, New Orleans, Louisiana, United States
	Weifa Liang , Richard P. Brent , Hong Shen, Fully Dynamic Maintenance of k-Connectivity in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.12 n.8, p.846-864, August 2001
	David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Journal of Experimental Algorithmics (JEA), 2, p.5-es, 1997
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	Daniele Frigioni , Tobias Miller , Christos Zaroliagis, An Experimental Study of Dynamic Algorithms for Transitive Closure, Journal of Experimental Algorithmics (JEA), 6, p.9-es, 2001
	David Alberts , Monika Rauch Henzinger, Average case analysis of dynamic graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.312-321, January 22-24, 1995, San Francisco, California, United States