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

DOI10.1007/s00453-012-9621-yzbMath1264.68068OpenAlexW2083795876MaRDI QIDQ1949751

Neelesh Khanna, Surender Baswana

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

shortest pathdistanceoracleapproximate distance

Mathematics Subject Classification ID

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

Related Items

Improved Purely Additive Fault-Tolerant Spanners ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Fault-tolerant approximate shortest-path trees ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Incremental distance products via faulty shortest paths ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• All-Pairs Small-Stretch Paths
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• Fast Algorithms for Finding Nearest Common Ancestors
• Oracles for Distances Avoiding a Failed Node or Link
• Approximate distance oracles
• f-Sensitivity Distance Oracles and Routing Schemes
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• All-Pairs Almost Shortest Paths
• A nearly optimal oracle for avoiding failed vertices and edges
• Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
• A new approach to dynamic all pairs shortest paths
• Finding the K Shortest Loopless Paths in a Network
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Automata, Languages and Programming