Fully dynamic biconnectivity in graphs
Henzinger MH. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
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.
If 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.
Publishing Year
Date Published
1995-06-01
Journal Title
Algorithmica
Publisher
Springer Nature
Volume
13
Issue
6
Page
503-538
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH. Fully dynamic biconnectivity in graphs. Algorithmica. 1995;13(6):503-538. doi:10.1007/bf01189067
Henzinger, M. H. (1995). Fully dynamic biconnectivity in graphs. Algorithmica. Springer Nature. https://doi.org/10.1007/bf01189067
Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica. Springer Nature, 1995. https://doi.org/10.1007/bf01189067.
M. H. Henzinger, “Fully dynamic biconnectivity in graphs,” Algorithmica, vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.
Henzinger MH. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538.
Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica, vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:10.1007/bf01189067.