DocumentCode :
2531030
Title :
Parametric and kinetic minimum spanning trees
Author :
Agarwal, Pankaj K. ; Eppstein, David ; Guibas, Leonidas J. ; Henzinger, Monika R.
Author_Institution :
Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
fYear :
1998
fDate :
8-11 Nov 1998
Firstpage :
596
Lastpage :
605
Abstract :
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter λ and wish to compute the sequence of minimum spanning trees generated as λ varies. We also consider the kinetic minimum spanning tree problem, in which λ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n2/3log4/3) per combinatorial change in the tree (or randomized O(n2/3log4/3 n) per change). Our time bounds reduce to O(n1/2log3/2 n) per change (O(n1/2 log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n1/4log3/2 n) per change (O(n1/4 log n) randomized) for planar graphs with weight changes but no insertions or deletions
Keywords :
computational geometry; optimisation; trees (mathematics); deletions; edge insertions; edge weights; kinetic minimum spanning trees; linear functions; parametric minimum spanning tree problem; weight functions; Computer science; Costs; Kinetic theory; Military computing; Stochastic processes; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
ISSN :
0272-5428
Print_ISBN :
0-8186-9172-7
Type :
conf
DOI :
10.1109/SFCS.1998.743510
Filename :
743510
Link To Document :
بازگشت