---
_id: '11803'
abstract:
- lang: eng
  text: We present the first fully dynamic algorithm for maintaining a minimum spanning
    tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log
    n) amortized time per update operation. The algorithm is fairly simple and deterministic.
    An immediate consequence is the first fully dynamic deterministic algorithm for
    maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per
    update, with O(1) worst case time per query.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Valerie
  full_name: King, Valerie
  last_name: King
citation:
  ama: 'Henzinger M, King V. Maintaining minimum spanning trees in dynamic graphs.
    In: <i>24th International Colloquium on Automata, Languages and Programming</i>.
    Vol 1256. Springer Nature; 1997:594–604. doi:<a href="https://doi.org/10.1007/3-540-63165-8_214">10.1007/3-540-63165-8_214</a>'
  apa: 'Henzinger, M., &#38; King, V. (1997). Maintaining minimum spanning trees in
    dynamic graphs. In <i>24th International Colloquium on Automata, Languages and
    Programming</i> (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature. <a
    href="https://doi.org/10.1007/3-540-63165-8_214">https://doi.org/10.1007/3-540-63165-8_214</a>'
  chicago: Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees
    in Dynamic Graphs.” In <i>24th International Colloquium on Automata, Languages
    and Programming</i>, 1256:594–604. Springer Nature, 1997. <a href="https://doi.org/10.1007/3-540-63165-8_214">https://doi.org/10.1007/3-540-63165-8_214</a>.
  ieee: M. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic graphs,”
    in <i>24th International Colloquium on Automata, Languages and Programming</i>,
    Bologna, Italy, 1997, vol. 1256, pp. 594–604.
  ista: 'Henzinger M, King V. 1997. Maintaining minimum spanning trees in dynamic
    graphs. 24th International Colloquium on Automata, Languages and Programming.
    ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
    vol. 1256, 594–604.'
  mla: Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees in
    Dynamic Graphs.” <i>24th International Colloquium on Automata, Languages and Programming</i>,
    vol. 1256, Springer Nature, 1997, pp. 594–604, doi:<a href="https://doi.org/10.1007/3-540-63165-8_214">10.1007/3-540-63165-8_214</a>.
  short: M. Henzinger, V. King, in:, 24th International Colloquium on Automata, Languages
    and Programming, Springer Nature, 1997, pp. 594–604.
conference:
  end_date: 1997-07-11
  location: Bologna, Italy
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 1997-07-07
date_created: 2022-08-11T13:35:06Z
date_published: 1997-07-01T00:00:00Z
date_updated: 2024-11-06T12:13:35Z
day: '01'
doi: 10.1007/3-540-63165-8_214
extern: '1'
intvolume: '      1256'
language:
- iso: eng
month: '07'
oa_version: None
page: 594–604
publication: 24th International Colloquium on Automata, Languages and Programming
publication_identifier:
  eisbn:
  - '9783540691945'
  eissn:
  - 1611-3349
  isbn:
  - '9783540631651'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maintaining minimum spanning trees in dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1256
year: '1997'
...