---
_id: '11910'
abstract:
- lang: eng
  text: "We state a new sampling lemma and use it to improve the running time of dynamic
    graph algorithms.\r\n\r\nFor the dynamic connectivity problem the previously best
    randomized algorithm takes expected time O(log3 n) per update, amortized over
    Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2
    n). There exists a lower bound in the cell probe model for the time per operation
    of Ω(log n/ log log n) for this problem.\r\n\r\nSimilarly improved running times
    are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness."
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: Mikkel
  full_name: Thorup, Mikkel
  last_name: Thorup
citation:
  ama: 'Henzinger MH, Thorup M. Improved sampling with applications to dynamic graph
    algorithms. In: <i>23rd International Colloquium on Automata, Languages, and Programming</i>.
    Vol 1099. Springer Nature; 1996:290-299. doi:<a href="https://doi.org/10.1007/3-540-61440-0_136">10.1007/3-540-61440-0_136</a>'
  apa: 'Henzinger, M. H., &#38; Thorup, M. (1996). Improved sampling with applications
    to dynamic graph algorithms. In <i>23rd International Colloquium on Automata,
    Languages, and Programming</i> (Vol. 1099, pp. 290–299). Paderborn, Germany: Springer
    Nature. <a href="https://doi.org/10.1007/3-540-61440-0_136">https://doi.org/10.1007/3-540-61440-0_136</a>'
  chicago: Henzinger, Monika H, and Mikkel Thorup. “Improved Sampling with Applications
    to Dynamic Graph Algorithms.” In <i>23rd International Colloquium on Automata,
    Languages, and Programming</i>, 1099:290–99. Springer Nature, 1996. <a href="https://doi.org/10.1007/3-540-61440-0_136">https://doi.org/10.1007/3-540-61440-0_136</a>.
  ieee: M. H. Henzinger and M. Thorup, “Improved sampling with applications to dynamic
    graph algorithms,” in <i>23rd International Colloquium on Automata, Languages,
    and Programming</i>, Paderborn, Germany, 1996, vol. 1099, pp. 290–299.
  ista: 'Henzinger MH, Thorup M. 1996. Improved sampling with applications to dynamic
    graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming.
    ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
    vol. 1099, 290–299.'
  mla: Henzinger, Monika H., and Mikkel Thorup. “Improved Sampling with Applications
    to Dynamic Graph Algorithms.” <i>23rd International Colloquium on Automata, Languages,
    and Programming</i>, vol. 1099, Springer Nature, 1996, pp. 290–99, doi:<a href="https://doi.org/10.1007/3-540-61440-0_136">10.1007/3-540-61440-0_136</a>.
  short: M.H. Henzinger, M. Thorup, in:, 23rd International Colloquium on Automata,
    Languages, and Programming, Springer Nature, 1996, pp. 290–299.
conference:
  end_date: 1996-07-12
  location: Paderborn, Germany
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 1996-07-08
date_created: 2022-08-18T06:42:24Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2023-02-14T07:57:14Z
day: '01'
doi: 10.1007/3-540-61440-0_136
extern: '1'
intvolume: '      1099'
language:
- iso: eng
month: '07'
oa_version: None
page: 290-299
publication: 23rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
  eisbn:
  - '9783540685807'
  eissn:
  - 1611-3349
  isbn:
  - '9783540614401'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved sampling with applications to dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1099
year: '1996'
...