---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: P. K.
foaf_name: Agarwal, P. K.
foaf_surname: Agarwal
- foaf_Person:
foaf_givenName: D.
foaf_name: EppsteinL. J. Guibas, D.
foaf_surname: EppsteinL. J. Guibas
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
bibo_doi: 10.1109/SFCS.1998.743510
dct_date: 1998^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0272-5428
- http://id.crossref.org/issn/0-8186-9172-7
dct_language: eng
dct_title: Parametric and kinetic minimum spanning trees@
...