Data structures for on-line updating of minimum spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Data structures for on-line updating of minimum spanning trees

Full text

Pdf (587 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the fifteenth annual ACM symposium on Theory of computing table of contents

Pages: 252 - 257

Year of Publication: 1983

ISBN:0-89791-099-0

Author

Greg N. Frederickson

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/800061.808754 What is a DOI?

ABSTRACT

Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take O((@@@@)m) time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of O ((log m)2).

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	D Cherilon and R. Tarjan, Finding minimum spanning trees, SIAM J. Comput. 5 (1976) 724-742.
	3	F. Chin and D. Houck, Algorithms for updating minimum spanning trees, J. Comp. Sys. Sci. 16 (1978) 333-344.
	4	G.N. Frederickson and M.A. Srinivas, Data structures for updating constrained spanning trees, manuscript in preparation (1983).
	5	Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981 [doi>10.1145/322234.322235]
	6	F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. (1969).
	7	M.H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comp. Sys. Sci. 23, 2 (October 1981) 166-204.
	8	P.M. Spira and A. Pan, On finding and updating spanning trees and shortest paths, SIAM J. Comput. 4, 3 (September 1975) 375-380.
	9	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
	10	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
	11	A.C. Yao, An O (E loglog V) algorithm for finding minimum spanning trees, Inf. Proc. Lett. 4 (1975) 21-23.

CITED BY 10

	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
	Mikkel Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.343-350, May 21-23, 2000, Portland, Oregon, 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
	Raj Iyer , David Karger , Hariharan Rahul , Mikkel Thorup, An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms, Journal of Experimental Algorithmics (JEA), 6, p.4-es, 2001
	Mikkel Thorup, Fully-dynamic min-cut, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.224-230, July 2001, Hersonissos, Greece
	Greg N. Frederickson , Mandayam A. Srinivas, Data structures for on-line updating of matroid intersection solutions, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.383-390, December 1984
	D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States
	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada
	Bambang N. Prastowo, Toward automation of generating incremental computation mechanisms, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.55, October 31-November 03, 1994, Toronto, Ontario, Canada
	Mohan Krishnamoorthy , Andreas T. Ernst , Yazid M. Sharaiha, Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree, Journal of Heuristics, v.7 n.6, p.587-611, November 2001