Generic Single Edge Fault Tolerant Exact Distance Oracle

Show simple item record Gupta, Manoj Singh, Aditi 2018-05-15T10:46:18Z 2018-05-15T10:46:18Z 2018-05
dc.identifier.citation Gupta, Manoj and Singh, Aditi,"Generic single edge fault tolerant exact distance Oracle", arXiv, Cornell University Library, DOI: arXiv:1805.00190, May 2018. en_US
dc.description.abstract Given an undirected unweighted graph G and a source set S of |S|=? sources, we want to build a data structure which can process the following query {\sc Q}(s,t,e): find the shortest distance from s to t avoiding an edge e, where s?S and t?V. When ?=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n2) space (O~(?) hides poly logn factor.) and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{\`o} et. al. (STACS 2018) designed a data-structure of size O~(?1/2n3/2) with the query time of O(n?????) for the above problem. We improve their result by designing a data-structure of size O~(?1/2n3/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 the {\em replacement} paths ending at a vertex t are disjoint, then the number of such paths is O(n?????). This eventually gives a bound of O(nn?????)=O(?1/2n3/2) for their problem. {\em 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 \textbf{may not} be disjoint. This result is the crux of our paper and may be of independent interest.?
dc.description.statementofresponsibility by Manoj Gupta and Aditi Singh
dc.language.iso en en_US
dc.publisher Cornell University Library en_US
dc.subject Data Structures en_US
dc.subject Algorithms en_US
dc.title Generic Single Edge Fault Tolerant Exact Distance Oracle en_US
dc.type Preprint en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account