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

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

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

shortest path; distance; oracle; approximate distance

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C12: Distance in graphs

68P05: Data structures

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