Improved data structures for fully dynamic biconnectivity

Henzinger MH. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English

Scopus indexed
Abstract
We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A 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 𝑂(π‘›βˆš) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min m2/3 ,n}) in general graphs and 𝑂(π‘›βˆš) in plane graphs for fully dynamic biconnectivity. We improve the later running times to 𝑂(π‘šlogπ‘›β€Ύβ€Ύβ€Ύβ€Ύβ€Ύβ€Ύβ€Ύβˆš) 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).
Publishing Year
Date Published
2000-11-01
Journal Title
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics
Volume
29
Issue
6
Page
1761-1815
ISSN
eISSN
IST-REx-ID

Cite this

Henzinger MH. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 2000;29(6):1761-1815. doi:10.1137/s0097539794263907
Henzinger, M. H. (2000). Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539794263907
Henzinger, Monika H. β€œImproved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2000. https://doi.org/10.1137/s0097539794263907.
M. H. Henzinger, β€œImproved data structures for fully dynamic biconnectivity,” SIAM Journal on Computing, vol. 29, no. 6. Society for Industrial & Applied Mathematics, pp. 1761–1815, 2000.
Henzinger MH. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815.
Henzinger, Monika H. β€œImproved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing, vol. 29, no. 6, Society for Industrial & Applied Mathematics, 2000, pp. 1761–815, doi:10.1137/s0097539794263907.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar