Lower bounds for fully dynamic connectivity problems in graphs
From MaRDI portal
Publication:1273940
DOI10.1007/PL00009228zbMath0915.68132MaRDI QIDQ1273940
Michael L. Fredman, Monika R. Henzinger
Publication date: 5 July 1999
Published in: Algorithmica (Search for Journal in Brave)
Related Items (11)
Dynamic connectivity in digital images ⋮ Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay ⋮ Optimal decremental connectivity in planar graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ The saga of minimum spanning trees ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Unnamed Item
This page was built for publication: Lower bounds for fully dynamic connectivity problems in graphs
