License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.42
URN: urn:nbn:de:0030-drops-169800
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16980/
Go to the corresponding LIPIcs Volume Portal

Dey, Dipan ; Gupta, Manoj

Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem

pdf-format:
LIPIcs-ESA-2022-42.pdf (0.8 MB)

Abstract

In a graph G with a source s, we design a distance oracle that can answer the following query: Query(s,t,e) - find the length of shortest path from a fixed source s to any destination vertex t while avoiding any edge e. We design a deterministic algorithm that builds such an oracle in Õ(m √n) time. Our oracle uses Õ(n √n) space and can answer queries in Õ(1) time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in Õ(m √n+n²) time.
Using our distance oracle, we also solve the single source replacement path problem (Ssrp problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the Ssrp problem. The running time of their algorithm is Õ(m √n + n²). In this paper, we show that the Ssrp problem can be solved in Õ(m √n + |ℛ|) time, where ℛ is the output set of the Ssrp problem in G. Our Ssrp algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of Ω(m √n) for any combinatorial algorithm that solves this problem.

BibTeX - Entry

@InProceedings{dey_et_al:LIPIcs.ESA.2022.42,
  author =	{Dey, Dipan and Gupta, Manoj},
  title =	{{Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16980},
  URN =		{urn:nbn:de:0030-drops-169800},
  doi =		{10.4230/LIPIcs.ESA.2022.42},
  annote =	{Keywords: distance sensitivity oracle, single-source replacement paths}
}

Keywords: distance sensitivity oracle, single-source replacement paths
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI