Improved deterministic algorithms for decremental reachability and strongly connected components

DOI10.1145/2483699.2483707MaRDI QIDQ2933657zbMATHOpenAlexFDO

Authors Jakub Łącki

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2483699.2483707

zbMATH Keywords

graph algorithmstransitive closuredynamic algorithmsstrongly connected componentsdecremental algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Recommendations

• scientific article; zbMATH DE number 6783482
• Decremental strongly connected components and single-source reachability in near-linear time
• Decremental strongly-connected components and single-source reachability in near-linear time
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Decremental single-source reachability in planar digraphs

Cited in

(9)

• Accelerating the calculation of makespan used in scheduling improvement heuristics
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Decremental strongly-connected components and single-source reachability in near-linear time
• Decremental SPQR-trees for Planar Graphs
• scientific article; zbMATH DE number 6783482 (Why is no real title available?)
• Tight localizations of feedback sets
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Decremental strongly connected components and single-source reachability in near-linear time
• Where is this leading me: stationary point and equilibrium analysis for self-modeling network models

This page was built for publication: Improved deterministic algorithms for decremental reachability and strongly connected components

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