Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs

DOI10.1007/S00453-012-9621-YMaRDI QIDQ1949751zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

distanceshortest pathoracleapproximate distance

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Distance in graphs (05C12) Paths and cycles (05C38)

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

Cites work

• scientific article; zbMATH DE number 1962826 (Why is no real title available?)
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A data structure for dynamic trees
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• A nearly optimal oracle for avoiding failed vertices and edges
• A new approach to dynamic all pairs shortest paths
• All-Pairs Almost Shortest Paths
• All-pairs small-stretch paths
• Approximate distance oracles
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Automata, Languages and Programming
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Faster algorithms for all-pairs approximate shortest paths in undirected graphs
• Finding the K Shortest Loopless Paths in a Network
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Finding the most vital node of a shortest path.
• Oracles for Distances Avoiding a Failed Node or Link
• The k most vital arcs in the shortest path problem
• \(f\)-sensitivity distance oracles and routing schemes

Cited in

(22)

• New extremal bounds for reachability and strong-connectivity preservers under failures
• 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
• Deterministic fault-tolerant connectivity labeling scheme
• Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs
• Compact distance oracles with large sensitivity and low stretch
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• Fault-tolerant approximate shortest-path trees
• Path-fault-tolerant approximate shortest-path trees
• A nearly linear time construction of approximate single-source distance sensitivity oracles
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Incremental distance products via faulty shortest paths
• Efficient oracles and routing schemes for replacement paths
• Conditional hardness for sensitivity problems
• Approximate distance sensitivity oracles in subquadratic space
• Fault-tolerant bounded flow preservers
• 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)