---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- 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.1007/bf01189067
bibo_issue: '6'
bibo_volume: 13
dct_date: 1995^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0178-4617
- http://id.crossref.org/issn/1432-0541
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Fully dynamic biconnectivity in graphs@
...