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

DOI10.1007/S00453-012-9621-YzbMATH Open1264.68068OpenAlexW2083795876MaRDI QIDQ1949751FDOQ1949751

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

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

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)

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 ² ) time
• Title not available (Why is that?)
• f-Sensitivity Distance Oracles and Routing Schemes
• Title not available (Why is that?)
• Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Cited In (15)

• A nearly optimal oracle for avoiding failed vertices and edges
• Efficient Oracles and Routing Schemes for Replacement Paths
• Approximate distance sensitivity oracles in subquadratic space
• Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal
• Title not available (Why is that?)
• Compact distance oracles with large sensitivity and low stretch
• Improved Purely Additive Fault-Tolerant Spanners
• Fault-tolerant approximate shortest-path trees
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Approximate distance sensitivity oracles in subquadratic space
• Incremental distance products via faulty shortest paths
• Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
• Multiple-edge-fault-tolerant approximate shortest-path trees
• An efficient strongly connected components algorithm in the fault tolerant model
• Path-Fault-Tolerant Approximate Shortest-Path Trees

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)