Improved Dynamic Reachability Algorithms for Directed Graphs

DOI10.1137/060650271zbMath1225.68276OpenAlexW2097490969MaRDI QIDQ3532572

Liam Roditty, Uri Zwick

Publication date: 28 October 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a87d867fdf8496d1706e150be0ffc84fa14c92f3

zbMATH Keywords

transitive closuredynamic algorithmsstrongly connected components

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Related Items (20)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ Fast dynamic transitive closure with lookahead ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ On dynamic shortest paths problems ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Unnamed Item ⋮ Dynamic graph coloring ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Unnamed Item ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

This page was built for publication: Improved Dynamic Reachability Algorithms for Directed Graphs