---
res:
bibo_abstract:
- 'This paper presents an algorithm for the fully dynamic biconnectivity problem
whose running time is exponentially faster than all previously known solutions.
It is the first dynamic algorithm that answers biconnectivity queries in time
O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or
deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized
algorithm with the update time amortized update time O(log/sup 4/n). Only recently
the best deterministic result for this problem was improved to O(/spl radic/nlog/sup
2/n). We also give the first fully dynamic and a novel deletions-only transitive
closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo
algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the
average number of edges in the graph during the whole update sequence: The fully
dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl
radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup
/spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is
the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The
deletions-only algorithm answers queries in time O(n/logn). Its amortized update
time is O(nlog/sup 2/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
- foaf_Person:
foaf_givenName: V.
foaf_name: King, V.
foaf_surname: King
bibo_doi: 10.1109/SFCS.1995.492668
dct_date: 1995^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0272-5428
- http://id.crossref.org/issn/0-8186-7183-1
dct_language: eng
dct_publisher: Institute of Electrical and Electronics Engineers@
dct_title: Fully dynamic biconnectivity and transitive closure@
...