Lower bounds for dynamic connectivity

DOI10.1145/1007352.1007435zbMATH Open1192.68185OpenAlexW2153217785MaRDI QIDQ3580993FDOQ3580993

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

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

Mathematics Subject Classification ID

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

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
• Cell-probe lower bounds for dynamic problems via a new communication model
• On dynamic bit-probe complexity
• 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)