---
_id: '11682'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
author:
- first_name: P. K.
  full_name: Agarwal, P. K.
  last_name: Agarwal
- first_name: D.
  full_name: EppsteinL. J. Guibas, D.
  last_name: EppsteinL. J. Guibas
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Agarwal PK, EppsteinL. J. Guibas D, Henzinger MH. Parametric and kinetic minimum
    spanning trees. In: <i>Proceedings of the 39th Annual Symposium on Foundations
    of Computer Science</i>. ; 1998:596-605. doi:<a href="https://doi.org/10.1109/SFCS.1998.743510">10.1109/SFCS.1998.743510</a>'
  apa: Agarwal, P. K., EppsteinL. J. Guibas, D., &#38; Henzinger, M. H. (1998). Parametric
    and kinetic minimum spanning trees. In <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i> (pp. 596–605). Palo Alto, CA, United States.
    <a href="https://doi.org/10.1109/SFCS.1998.743510">https://doi.org/10.1109/SFCS.1998.743510</a>
  chicago: Agarwal, P. K., D. EppsteinL. J. Guibas, and Monika H Henzinger. “Parametric
    and Kinetic Minimum Spanning Trees.” In <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i>, 596–605, 1998. <a href="https://doi.org/10.1109/SFCS.1998.743510">https://doi.org/10.1109/SFCS.1998.743510</a>.
  ieee: P. K. Agarwal, D. EppsteinL. J. Guibas, and M. H. Henzinger, “Parametric and
    kinetic minimum spanning trees,” in <i>Proceedings of the 39th Annual Symposium
    on Foundations of Computer Science</i>, Palo Alto, CA, United States, 1998, pp.
    596–605.
  ista: 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.
  mla: Agarwal, P. K., et al. “Parametric and Kinetic Minimum Spanning Trees.” <i>Proceedings
    of the 39th Annual Symposium on Foundations of Computer Science</i>, 1998, pp.
    596–605, doi:<a href="https://doi.org/10.1109/SFCS.1998.743510">10.1109/SFCS.1998.743510</a>.
  short: P.K. Agarwal, D. EppsteinL. J. Guibas, M.H. Henzinger, in:, Proceedings of
    the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596–605.
conference:
  end_date: 1998-11-11
  location: Palo Alto, CA, United States
  name: Annual IEEE Symposium on Foundations of Computer Science
  start_date: 1998-11-08
date_created: 2022-07-28T07:21:34Z
date_published: 1998-09-01T00:00:00Z
date_updated: 2023-02-09T11:28:52Z
day: '01'
doi: 10.1109/SFCS.1998.743510
extern: '1'
language:
- iso: eng
month: '09'
oa_version: None
page: 596-605
publication: Proceedings of the 39th Annual Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - 0-8186-9172-7
  issn:
  - 0272-5428
publication_status: published
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parametric and kinetic minimum spanning trees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1998'
...