Lower bounds for fully dynamic connectivity problems in graphs

Henzinger MH, Fredman ML. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 22(3), 351–362.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English

Scopus indexed
Author
Henzinger, MonikaISTA ; Fredman, M. L.
Abstract
We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems.
Publishing Year
Date Published
1998-11-01
Journal Title
Algorithmica
Publisher
Springer Nature
Acknowledgement
.
Volume
22
Issue
3
Page
351-362
ISSN
eISSN
IST-REx-ID

Cite this

Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 1998;22(3):351-362. doi:10.1007/pl00009228
Henzinger, M. H., & Fredman, M. L. (1998). Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009228
Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009228.
M. H. Henzinger and M. L. Fredman, “Lower bounds for fully dynamic connectivity problems in graphs,” Algorithmica, vol. 22, no. 3. Springer Nature, pp. 351–362, 1998.
Henzinger MH, Fredman ML. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica. 22(3), 351–362.
Henzinger, Monika H., and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.” Algorithmica, vol. 22, no. 3, Springer Nature, 1998, pp. 351–62, doi:10.1007/pl00009228.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar