Lower bounds for fully dynamic connectivity problems in graphs

DOI10.1007/PL00009228MaRDI QIDQ1273940zbMATH OpenFDO

Authors Michael L. Fredman, Monika R. Henzinger

Publication date 5 July 1999

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

dynamic connectivity problems

Mathematics Subject Classification ID

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

Recommendations

• Improved data structures for fully dynamic biconnectivity
• Lower bounds for dynamic connectivity
• Near-optimal fully-dynamic graph connectivity
• Faster deterministic fully-dynamic graph connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time

Cited in

(15)

• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
• Near-optimal fully-dynamic graph connectivity
• Dynamic connectivity for axis-parallel rectangles
• Dynamic connectivity in digital images
• The saga of minimum spanning trees
• Upper and lower bounds on the power of advice
• Constant-time dynamic weight approximation for minimum spanning forest
• A little advice can be very helpful
• Optimal offline dynamic 2, 3-edge/vertex connectivity
• Optimal decremental connectivity in planar graphs
• Lower bounds for dynamic connectivity
• A fully dynamic algorithm for maintaining the transitive closure
• Dynamic graph connectivity in polylogarithmic worst case time
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
• Deterministic dynamic matching in \(O(1)\) update time

This page was built for publication: Lower bounds for fully dynamic connectivity problems in graphs

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