Gupta, Manoj ;
Singh, Aditi
Generic Single Edge Fault Tolerant Exact Distance Oracle
Abstract
Given an undirected unweighted graph G and a source set S of S = sigma sources, we want to build a data structure which can process the following query Q(s,t,e): find the shortest distance from s to t avoiding an edge e, where s in S and t in V. When sigma=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n^2) space and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{ò} et. al. (STACS 2018) designed a datastructure of size O~(sigma^{1/2}n^{3/2}) with the query time of O(sqrt{n sigma}) for the above problem. We improve their result by designing a datastructure of size O~(sigma^{1/2} n^{3/2}) that can answer queries in O~(1) time.
In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of replacement paths ending at a vertex t are disjoint, then the number of such paths is O(sqrt{n sigma}). This eventually gives a bound of O(n sqrt{n sigma}) = O(sigma^{1/2}n^{3/2}) for their problem. Disjointness of detours is a very crucial property used in the above result. We show a similar result for a subset of replacement path which may not be disjoint. This result is the crux of our paper and may be of independent interest.
BibTeX  Entry
@InProceedings{gupta_et_al:LIPIcs:2018:9076,
author = {Manoj Gupta and Aditi Singh},
title = {{Generic Single Edge Fault Tolerant Exact Distance Oracle}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {72:172:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9076},
URN = {urn:nbn:de:0030drops90766},
doi = {10.4230/LIPIcs.ICALP.2018.72},
annote = {Keywords: Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, DataStructures}
}
04.07.2018
Keywords: 

Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, DataStructures 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 