dc.contributor.author Fredman, Michael L. en_US dc.contributor.author Rauch, Monika H. en_US dc.date.accessioned 2007-04-23T16:35:26Z dc.date.available 2007-04-23T16:35:26Z dc.date.issued 1994-04 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1420 en_US dc.identifier.uri https://hdl.handle.net/1813/6202 dc.description.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 $\Omega(\log n/k(\log\log n + \log b))$ per edge insertion or deletion or per 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 $\Omega(\log n/(\log\log n + \log b))$ per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for dynamic connectivity problems. en_US dc.format.extent 985471 bytes dc.format.extent 314727 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Lower Bounds for Dynamic Connectivity Problems in Graphs en_US dc.type technical report en_US
﻿