Paper by Erik D. Demaine
- Mihai Pǎtraşcu and Erik D. Demaine, “Lower Bounds for Dynamic Connectivity”, in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), Chicago, Illinois, June 13–15, 2004, pages 546–553.
We prove an Ω(lg n) cell-probe lower bound on maintaining
connectivity in dynamic graphs, as well as a more general trade-off
between updates and queries. Our bound holds even if the graph is
formed by disjoint paths, and thus also applies to trees and plane
graphs. The bound is known to be tight for these restricted cases,
proving optimality of these data structures (e.g., Sleator and
Tarjan's dynamic trees). Our trade-off is known to be tight for trees,
and the best two data structures for dynamic connectivity in general
graphs are points on our trade-off curve. In this sense these two data
structures are optimal, and this tightness serves as strong evidence
that our lower bounds are the best possible.
From a more theoretical perspective, our result is the first
logarithmic cell-probe lower bound for any problem in the natural
class of dynamic language membership problems, breaking the long
standing record of Ω(lg n / lg lg n).
In this sense, our
result is the first data-structure lower bound that is “truly”
logarithmic, i.e., logarithmic in the problem size counted in bits.
Obtaining such a bound is listed as one of three major challenges for
future research by Miltersen  (the other two
challenges remain unsolved).
Our techniques form a general framework for proving
cell-probe lower bounds on dynamic data structures.
We show how our framework also applies to the partial-sums problem
to obtain a nearly complete understanding of the problem in cell-probe
and algebraic models, solving several previously posed open problems.
- This paper is also available from the ACM Digital Library.
- The paper is 8 pages.
- The paper is available in PostScript (320k), gzipped PostScript (135k), and PDF (148k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- DynamicConnectivity_SICOMP (Logarithmic Lower Bounds in the Cell-Probe Model)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by