Math @ Duke

Publications [#235605] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Eppstein, D; Guibas, LJ; Henzinger, MR, Parametric and kinetic minimum spanning trees,
in Thirty Ninth Annual Symposium on Foundations of Computer Science,
Annual Symposium on Foundations of Computer Science (Proceedings)
(1998),
pp. 596605
(last updated on 2018/08/21)
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/3 log4/3 n) per combinatorial change in the tree (or randomized O(n2/3 log n) per change). Our time bounds reduce to O(n1/2 log3/2 n) per change (O(n1/2log n) randomized) for planar graphs or other minorclosed families of graphs, and O(n1/4 log3/2 n) per change (O(n1/4 log n) randomized) for planar graphs with weight changes but no insertions or deletions.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

