Lower bounds for dynamic connectivity

DOI10.1145/1007352.1007435MaRDI QIDQ3580993zbMATH OpenOpenAlexFDO

Authors Mihai Patrascu, Erik D. Demaine

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007435

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds for fully dynamic connectivity problems in graphs
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• Near-optimal fully-dynamic graph connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time

Cited in

(9)

• Cell-probe lower bounds from online communication complexity
• Logarithmic Lower Bounds in the Cell-Probe Model
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
• On dynamic bit-probe complexity
• Cell-probe lower bounds for dynamic problems via a new communication model
• Faster Fully-Dynamic Minimum Spanning Forest
• Some lower bounds in dynamic networks with oblivious adversaries
• Don't rush into a union, take time to find your roots
• On the quantifier-free dynamic complexity of reachability

This page was built for publication: Lower bounds for dynamic connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580993)