Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
type: Item
instance of: scholarly article
title: Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
zbMATH Open document ID: 1264.68068
author: Surender Baswana
author: Neelesh Khanna
published in: Algorithmica
publication date: 2013-05-16T00:00:00Z
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 6163654
zbMATH Keywords: shortest path
zbMATH Keywords: distance
zbMATH Keywords: approximate distance
zbMATH Keywords: oracle
MaRDI profile type: Publication
full work available at URL: s00453-012-9621-y
OpenAlex ID: W2083795876
cites work: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
cites work: Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
cites work: Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
cites work: Q5417664
cites work: A nearly optimal oracle for avoiding failed vertices and edges
cites work: f-Sensitivity Distance Oracles and Routing Schemes
cites work: All-pairs small-stretch paths
cites work: A new approach to dynamic all pairs shortest paths
cites work: Oracles for Distances Avoiding a Failed Node or Link
cites work: All-Pairs Almost Shortest Paths
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Q4418662
cites work: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
cites work: The k most vital arcs in the shortest path problem
cites work: Finding the most vital node of a shortest path.
cites work: Automata, Languages and Programming
cites work: A data structure for dynamic trees
cites work: Approximate distance oracles
cites work: Finding the K Shortest Loopless Paths in a Network
DOI: 10.1007/S00453-012-9621-Y
description: scientific article; zbMATH DE number 6163654