License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.72
URN: urn:nbn:de:0030-drops-90766
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9076/
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 data-structure 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 data-structure 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:1--72:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9076},
URN = {urn:nbn:de:0030-drops-90766},
doi = {10.4230/LIPIcs.ICALP.2018.72},
annote = {Keywords: Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, Data-Structures}
}
|
Keywords: |
|
Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, Data-Structures |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
