TY - JOUR
T1 - Maintenance of a minimum spanning forest in a dynamic plane graph
AU - Eppstein, David
AU - Italiano, Giuseppe F.
AU - Tamassia, Roberto
AU - Tarjan, Robert E.
AU - Westbrook, Jeffery
AU - Yung, Moti
N1 - Funding Information:
*Research supported in part by NSF Grants CCR-88-14977, DCR-86-05962, CCR-90-09753, ONR Contract NOOO14-91-J-1463, DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant NSF-STC88-09648, and Esprit II Basic Research Actions Program of the European Communities Contract 3075. A preliminary version of this article appeared in the “Proceedings 1st ACM-SIAM Symposium on Discrete-Algorithms, San Francisco, CA, January 1990.” ‘This work was done while the author was at the Department of Computer Science, Columbia University, New York, NY 10027. *Partially supported by an IBM Graduate Fellowship. *This work done while the author was at the Department of Computer Science, Princeton University.
PY - 1992/3
Y1 - 1992/3
N2 - We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights and insertion and deletion of edges and vertices which are consistent with the given embedding. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithm runs in O(log n) time per operation and O(n) space. The algorithm can be used to maintain the connected components of a dynamic planar graph in O(logn) time per operation. We also show that any algorithm will need Ω(log n) amortized time per operation, given a set of machine operations that is fairly general.
AB - We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights and insertion and deletion of edges and vertices which are consistent with the given embedding. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithm runs in O(log n) time per operation and O(n) space. The algorithm can be used to maintain the connected components of a dynamic planar graph in O(logn) time per operation. We also show that any algorithm will need Ω(log n) amortized time per operation, given a set of machine operations that is fairly general.
UR - http://www.scopus.com/inward/record.url?scp=38249015356&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249015356&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(92)90004-V
DO - 10.1016/0196-6774(92)90004-V
M3 - Article
AN - SCOPUS:38249015356
SN - 0196-6774
VL - 13
SP - 33
EP - 54
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -