Khanna, Neelesh ;
Baswana, Surender
Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
Abstract
Let $G=(V,E)$ be any undirected graph on $V$ vertices and
$E$ edges. A path $\textbf{P}$ between any two vertices $u,v\in V$ is said to be $t$approximate shortest path if its length is at most $t$ times the length of the shortest path between $u$ and $v$.
We consider the problem of building a compact data structure for a
given graph $G$ which is capable of answering the following query for
any $u,v,z\in V$ and $t>1$.
\centerline{\em report $t$approximate shortest path between $u$ and $v$ when vertex $z$ fails}
We present data structures for the single source as well allpairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size {\em nearly} match the size of their best static counterparts.
BibTeX  Entry
@InProceedings{khanna_et_al:LIPIcs:2010:2481,
author = {Neelesh Khanna and Surender Baswana},
title = {{Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {513524},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2481},
URN = {urn:nbn:de:0030drops24812},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2481},
annote = {Keywords: Shortest path, distance, distance queries, oracle}
}
2010
Keywords: 

Shortest path, distance, distance queries, oracle 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 