TY - JOUR
AB - 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.
AU - Henzinger, Monika H
AU - Fredman, M. L.
ID - 11681
IS - 3
JF - Algorithmica
KW - Dynamic planarity testing
KW - Dynamic connectivity testing
KW - Lower bounds
KW - Cell probe model
SN - 0178-4617
TI - Lower bounds for fully dynamic connectivity problems in graphs
VL - 22
ER -