Decremental Dynamic Connectivity

DOI10.1006/JAGM.1999.1033MaRDI QIDQ4935307zbMATH OpenOpenAlexFDO

Authors Mikkel Thorup

Publication date 19 March 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1999.1033

zbMATH Keywords

\(k\)-edge-connectivity

Mathematics Subject Classification ID

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

Recommendations

• Optimal on-line decremental connectivity in trees
• scientific article; zbMATH DE number 1263228
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Optimal decremental connectivity in planar graphs
• Optimal decremental connectivity in planar graphs

Cited in

(9)

• Incomplete directed perfect phylogeny in linear time
• Dynamic connectivity for axis-parallel rectangles
• Optimal decremental connectivity in planar graphs
• Optimal on-line decremental connectivity in trees
• An Optimal Rebuilding Strategy for a Decremental Tree Problem
• Randomization for efficient dynamic graph algorithms (invited talk)
• Decremental strongly connected components and single-source reachability in near-linear time
• Optimal decremental connectivity in planar graphs
• Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study

This page was built for publication: Decremental Dynamic Connectivity

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