Decremental maintenance of strongly connected components

DOI10.1137/1.9781611973105.82MaRDI QIDQ5741791zbMATH OpenOpenAlexFDO

Authors Liam Roditty

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.82

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Decremental strongly connected components and single-source reachability in near-linear time
• Decremental strongly-connected components and single-source reachability in near-linear time
• Decremental data structures for connectivity and dominators in directed graphs
• scientific article; zbMATH DE number 6783482
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

Cited in

(9)

• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Decremental strongly connected components and single-source reachability in near-linear time
• Decremental data structures for connectivity and dominators in directed graphs
• An efficient strongly connected components algorithm in the fault tolerant model
• Strong connectivity in directed graphs under failures, with applications
• Decremental strongly-connected components and single-source reachability in near-linear time
• Maintaining triconnected components under node expansion
• An efficient strongly connected components algorithm in the fault tolerant model

This page was built for publication: Decremental maintenance of strongly connected components

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