Decremental Dynamic Connectivity

DOI10.1006/JAGM.1999.1033zbMATH Open0957.68091OpenAlexW2095571038MaRDI QIDQ4935307FDOQ4935307

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

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

zbMATH Keywords

\(k\)-edge-connectivity

Mathematics Subject Classification ID

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

Cited In (9)

• Incomplete directed perfect phylogeny in linear time
• Dynamic connectivity for axis-parallel rectangles
• Optimal decremental connectivity in planar graphs
• An Optimal Rebuilding Strategy for a Decremental Tree Problem
• Optimal on-line decremental connectivity in trees
• 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)