2026-08-11T00:06:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9076 2024-03-06T10:43:18Z ddc:004 open_access

Generic Single Edge Fault Tolerant Exact Distance Oracle Gupta, Manoj Singh, Aditi Fault Tolerant Algorithms Graph Algorithms Distance Oracles Data-Structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manoj Gupta and Aditi Singh 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.72 urn:nbn:de:0030-drops-90766 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.72 eng https://creativecommons.org/licenses/by/3.0/legalcode