Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
DOI10.1007/S00453-012-9621-YzbMATH Open1264.68068OpenAlexW2083795876MaRDI QIDQ1949751FDOQ1949751
Authors: Surender Baswana, Neelesh Khanna 
Publication date: 16 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9621-y
Recommendations
- Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs
- A nearly optimal oracle for avoiding failed vertices and edges
- scientific article; zbMATH DE number 6850433
- Path-fault-tolerant approximate shortest-path trees
- Generic single edge fault tolerant exact distance oracle
Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Distance in graphs (05C12) Paths and cycles (05C38)
Cites Work
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- The k most vital arcs in the shortest path problem
- Finding the most vital node of a shortest path.
- A data structure for dynamic trees
- Oracles for Distances Avoiding a Failed Node or Link
- Approximate distance oracles
- All-Pairs Almost Shortest Paths
- A nearly optimal oracle for avoiding failed vertices and edges
- A new approach to dynamic all pairs shortest paths
- Finding the K Shortest Loopless Paths in a Network
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Fast Algorithms for Finding Nearest Common Ancestors
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- All-pairs small-stretch paths
- Automata, Languages and Programming
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Title not available (Why is that?)
- \(f\)-sensitivity distance oracles and routing schemes
- A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
Cited In (16)
- A nearly optimal oracle for avoiding failed vertices and edges
- Approximate distance sensitivity oracles in subquadratic space
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Improved purely additive fault-tolerant spanners
- Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs
- Compact distance oracles with large sensitivity and low stretch
- Fault-tolerant approximate shortest-path trees
- Path-fault-tolerant approximate shortest-path trees
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Fault-tolerant subgraph for single-source reachability: general and optimal
- Approximate distance sensitivity oracles in subquadratic space
- Incremental distance products via faulty shortest paths
- Efficient oracles and routing schemes for replacement paths
- Conditional hardness for sensitivity problems
- Multiple-edge-fault-tolerant approximate shortest-path trees
- An efficient strongly connected components algorithm in the fault tolerant model
This page was built for publication: Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1949751)
