Parametric and kinetic minimum spanning trees

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 computethe 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(n.pow2(2/3).log(4/3).n) per combinatorial change in the tree (or randomized O(n.pow2(2/3).log(n)) per change). Our time bounds reduce to O(n.pow2(1/2).log(3/2).n) per change (O(n.pow2(1/2).log(n)) randomized) for planar graphs or other minor-closed families of graphs, and O(n.pow2(1/4).log(3/2).n) per change (O(n.pow2(1/4).log(n) randomized) for planar graphs with weight changes but no insertions or deletions.


Published in:
Proceedings of the 1998 39th Annual Symposium on Foundations of Computer Science, 596-605
Year:
1998
Publisher:
IEEE Comp Soc
Keywords:
Other identifiers:
Scopus: 2-s2.0-0032307211
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)