An efficient strongly connected components algorithm in the fault tolerant model
From MaRDI portal
Publication:666658
DOI10.1007/s00453-018-0452-3zbMath1418.68159arXiv1610.04010OpenAlexW2536112642MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items (2)
Mincut sensitivity data structures for the insertion of an edge ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications
Cites Work
- \(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
- Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
- 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
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Compact and Fast Sensitivity Oracles for Single-Source Distances
- Multiple Source Dual Fault Tolerant BFS Trees
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An efficient strongly connected components algorithm in the fault tolerant model
