A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time
From MaRDI portal
Publication:2810272
DOI10.1137/13093618XzbMath1342.05187OpenAlexW2401697020MaRDI QIDQ2810272
Publication date: 1 June 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/13093618x
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (3)
Upper and lower bounds for fully retroactive graph problems ⋮ Reachability preserving compression for dynamic graph ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Path-based depth-first search for strong and biconnected components
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Finding paths and deleting edges in directed acyclic graphs
- A strong-connectivity algorithm and its applications in data flow analysis
- Reachability in graph timelines
- Fast Algorithms for Finding Nearest Common Ancestors
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Efficiency of a Good But Not Linear Set Union Algorithm
- An experimental study of algorithms for fully dynamic transitive closure
- An Experimental Study of Dynamic Algorithms for Transitive Closure
- Maintaining shortest paths under deletions in weighted directed graphs
- Depth-First Search and Linear Graph Algorithms
- Lowest common ancestors in trees and directed acyclic graphs
- Dynamic graph connectivity in polylogarithmic worst case time
This page was built for publication: A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time
