---
_id: '11677'
abstract:
- lang: eng
  text: "We present an algorithm for maintaining the biconnected components of a graph
    during a sequence of edge insertions and deletions. It requires linear storage
    and preprocessing time. The amortized running time for insertions and for deletions
    isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form
    ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the
    first sublinear algorithm for this problem. We can also output all articulation
    points separating any two vertices efficiently.\r\n\r\nIf the input is a plane
    graph, the amortized running time for insertions and deletions drops toO(√n logn)
    and the query time isO(log2 n), wheren is the number of vertices in the graph.
    The best previously known solution takes timeO(n 2/3 ) per update or query."
article_processing_charge: No
article_type: original
author:
- 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: Henzinger M. Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>. 1995;13(6):503-538.
    doi:<a href="https://doi.org/10.1007/bf01189067">10.1007/bf01189067</a>
  apa: Henzinger, M. (1995). Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>.
    Springer Nature. <a href="https://doi.org/10.1007/bf01189067">https://doi.org/10.1007/bf01189067</a>
  chicago: Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>.
    Springer Nature, 1995. <a href="https://doi.org/10.1007/bf01189067">https://doi.org/10.1007/bf01189067</a>.
  ieee: M. Henzinger, “Fully dynamic biconnectivity in graphs,” <i>Algorithmica</i>,
    vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.
  ista: Henzinger M. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6),
    503–538.
  mla: Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>,
    vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:<a href="https://doi.org/10.1007/bf01189067">10.1007/bf01189067</a>.
  short: M. Henzinger, Algorithmica 13 (1995) 503–538.
date_created: 2022-07-27T14:50:46Z
date_published: 1995-06-01T00:00:00Z
date_updated: 2024-11-06T08:12:13Z
day: '01'
doi: 10.1007/bf01189067
extern: '1'
intvolume: '        13'
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 503-538
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic biconnectivity in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '1995'
...