Multiple-edge-fault-tolerant approximate shortest-path trees
From MaRDI portal
Publication:2072097
DOI10.1007/s00453-021-00879-8OpenAlexW3210632178MaRDI QIDQ2072097
Davide Bilò, Luciano Gualà, Guido Proietti, Stefano Leucci
Publication date: 1 February 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5719/
distance sensitivity oraclefully-dynamic minimum spanning treemultiple-edge fault-tolerant shortest-path tree
Analysis of algorithms (68W40) Algorithms in computer science (68Wxx) Data structures (68P05) Graph theory (05Cxx)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On resilient graph spanners
- \(f\)-sensitivity distance oracles and routing schemes
- On sparse spanners of weighted graphs
- Swapping a failing edge of a single source shortest paths tree is good and fast
- Vertex fault tolerant additive spanners
- Fault-tolerant approximate shortest-path trees
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Deterministic Dictionaries
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Dual Failure Resilient BFS Structure
- Maintaining information in fully dynamic trees with top trees
- Additive spanners and (α, β)-spanners
- Efficient Oracles and Routing Schemes for Replacement Paths
- Fast Algorithms for Finding Nearest Common Ancestors
- Improved Purely Additive Fault-Tolerant Spanners
- Path-Fault-Tolerant Approximate Shortest-Path Trees
- Approximate distance oracles
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Offline Algorithms for Dynamic Minimum Spanning Tree Problems
- Sparsification—a technique for speeding up dynamic graph algorithms
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Fault-Tolerant Approximate BFS Structures
- Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal
- Compact and Fast Sensitivity Oracles for Single-Source Distances
- A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
- Sparse Fault-Tolerant BFS Structures
- Multiple Source Dual Fault Tolerant BFS Trees
- A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
- A nearly optimal oracle for avoiding failed vertices and edges
- Sequential and Parallel Algorithms and Data Structures
- Exact Distance Oracles for Planar Graphs with Failing Vertices
- Approximate distance oracles with constant query time
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- New Additive Spanners
