---
res:
bibo_abstract:
- "We present fully dynamic algorithms for maintaining the biconnected components
in general and plane graphs.\r\n\r\nA fully dynamic algorithm maintains a graph
during a sequence of insertions and deletions of edges or isolated vertices. Let
m be the number of edges and n be the number of vertices in a graph. The time
per operation of the best deterministic algorithms is \U0001D442(\U0001D45B√)
in general graphs and O(log n) in plane graphs for fully dynamic connectivity
and O(min m2/3 ,n}) in general graphs and \U0001D442(\U0001D45B√) in plane graphs
for fully dynamic biconnectivity. We improve the later running times to \U0001D442(\U0001D45Alog\U0001D45B‾‾‾‾‾‾‾√)
in general graphs and O(log 2n ) in plane graphs. Our algorithm for general graphscan
also find the biconnected components of all vertices in time O(n).@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.1137/s0097539794263907
bibo_issue: '6'
bibo_volume: 29
dct_date: 2000^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0097-5397
- http://id.crossref.org/issn/1095-7111
dct_language: eng
dct_publisher: Society for Industrial & Applied Mathematics@
dct_title: Improved data structures for fully dynamic biconnectivity@
...