Near-optimal fully-dynamic graph connectivity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Near-optimal fully-dynamic graph connectivity

Full text

Pdf (913 KB)

Source

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

Portland, Oregon, United States

Pages: 343 - 350

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Mikkel Thorup

AT&T Labs--Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 130, Citation Count: 13

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/335305.335345 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 , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
	2	Greg N. Frederickson, Data structures for on-line updating of minimum spanning trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.252-257, December 1983 [doi>10.1145/800061.808754]
	3	M. Fredman and M. Henzinger. Lower bounds for fully dynamic connectivity problems in graphs. A!gorithmica, 22(3):351-362, 1998.
	4	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 [doi>10.1145/225058.225269]
	5	Monika R. Henzinger , Mikkel Thorup, Sampling to provide or to bound: with applications to fully dynamic graph algorithms, Random Structures & Algorithms, v.11 n.4, p.369-379, Dec. 1997
	6	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 [doi>10.1145/276698.276715]
	7	Peter Bro Miltersen , Sairam Subramanian , Jeffrey Scott Vitter , Roberto Tamassia, Complexity models for incremental computation, Theoretical Computer Science, v.130 n.1, p.203-236, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90159-7]
	8	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]
	9	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	10	Mikkel Thorup, Decremental dynamic connectivity, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.305-313, January 05-07, 1997, New Orleans, Louisiana, United States

CITED BY 13

	David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Christos D. Zaroliagis, Implementations and experimental studies of dynamic graph algorithms, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001
	Timothy M. Chan, Dynamic subgraph connectivity with geometric applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	David Eppstein , M. Gopi, Single-strip triangulation of manifolds with arbitrary topology, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Michiel Smid , Rahul Ray , Ulrich Wendt , Katharina Lange, Computing large planar regions in terrains, with an application to fracture surfaces, Discrete Applied Mathematics, v.139 n.1-3, p.253-264, 30 April 2004
	Mihai Pǎtraşcu , Erik D. Demaine, Lower bounds for dynamic connectivity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Stefan Funke , Theocharis Malamatos , Rahul Ray, Finding planar regions in a terrain: in practice and with a guarantree, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Timothy M. Chan, Finding the shortest bottleneck edge in a parametric minimum spanning tree, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Mihai Patracu , Corina E. Tarnia, On dynamic bit-probe complexity, Theoretical Computer Science, v.380 n.1-2, p.127-142, June, 2007
	Ignaz Rutter , Alexander Wolff, Computing large matchings fast, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.183-192, January 20-22, 2008, San Francisco, California
	Harish Doraiswamy , Vijay Natarajan, Efficient algorithms for computing Reeb graphs, Computational Geometry: Theory and Applications, v.42 n.6-7, p.606-616, August, 2009
	Henk Meijer , Yurai Núòez-Rodríguez , David Rappaport, An algorithm for computing simple k-factors, Information Processing Letters, v.109 n.12, p.620-625, May, 2009