An efficient strongly connected components algorithm in the fault tolerant model
From MaRDI portal
Publication:666658
DOI10.1007/s00453-018-0452-3zbMath1418.68159arXiv1610.04010MaRDI QIDQ666658
Surender Baswana, Keerti Choudhary, Liam Roditty
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.04010
68R10: Graph theory (including graph drawing) in computer science
68M15: Reliability, testing and fault tolerance of networks and computer systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(f\)-sensitivity distance oracles and routing schemes
- Finding paths and deleting edges in directed acyclic graphs
- A data structure for dynamic trees
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Fault-tolerant compact routing schemes for general graphs
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Dual Failure Resilient BFS Structure
- Sparse Fault-Tolerant BFS Trees
- Connectivity oracles for failure prone graphs
- Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fault-tolerant spanners
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Improved Purely Additive Fault-Tolerant Spanners
- Oracles for Distances Avoiding a Failed Node or Link
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Connectivity Oracles for Graphs Subject to Vertex Failures
- (1 + ∊)-Approximate f-Sensitive Distance Oracles
- Strong Connectivity in Directed Graphs under Failures, with Applications
- A nearly optimal oracle for avoiding failed vertices and edges
- An Experimental Study of Dynamic Algorithms for Transitive Closure
- Fault tolerant subgraph for single source reachability: generic and optimal
- Depth-First Search and Linear Graph Algorithms
- Dynamic graph connectivity in polylogarithmic worst case time
- Decremental maintenance of strongly connected components
