Parametric and kinetic minimum spanning trees
Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. 1998. Parametric and kinetic minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science, 596–605.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Agarwal, P. K.;
EppsteinL. J. Guibas, D.;
Henzinger, MonikaISTA
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 /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ 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/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.
Publishing Year
Date Published
1998-09-01
Proceedings Title
Proceedings of the 39th Annual Symposium on Foundations of Computer Science
Page
596-605
Conference
Annual IEEE Symposium on Foundations of Computer Science
Conference Location
Palo Alto, CA, United States
Conference Date
1998-11-08 – 1998-11-11
ISBN
ISSN
IST-REx-ID
Cite this
Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. ; 1998:596-605. doi:10.1109/SFCS.1998.743510
Agarwal, P. K., EppsteinL. J. Guibas, D., & Henzinger, M. H. (1998). Parametric and kinetic minimum spanning trees. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (pp. 596–605). Palo Alto, CA, United States. https://doi.org/10.1109/SFCS.1998.743510
Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika H Henzinger. “Parametric and Kinetic Minimum Spanning Trees.” In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 596–605, 1998. https://doi.org/10.1109/SFCS.1998.743510.
P. K. Agarwal, D. EppsteinL. J. Guibas, and M. H. Henzinger, “Parametric and kinetic minimum spanning trees,” in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, United States, 1998, pp. 596–605.
Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. 1998. Parametric and kinetic minimum spanning trees. Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science, 596–605.
Agarwal, P. K., et al. “Parametric and Kinetic Minimum Spanning Trees.” Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596–605, doi:10.1109/SFCS.1998.743510.