Search Results

Documents authored by Dey, Dipan

Document
DOI: 10.4230/LIPIcs.ESA.2024.45
Near Optimal Dual Fault Tolerant Distance Oracle

Authors: Dipan Dey and Manoj Gupta

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set F of two edges, as well as a source node s and a destination node t, our oracle returns the length of the shortest path from s to t that avoids F in O(1) time with a high probability. The space complexity of our oracle is Õ(n²) , making it nearly optimal in terms of both space and query time. Prior to our work, Pettie and Duan [SODA 2009] designed a dual fault-tolerant distance oracle that required Õ(n²) space and O(log n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.
Cite as

Dipan Dey and Manoj Gupta. Near Optimal Dual Fault Tolerant Distance Oracle. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2024.45,
  author =	{Dey, Dipan and Gupta, Manoj},
  title =	{{Near Optimal Dual Fault Tolerant Distance Oracle}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{45:1--45:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.45},
  URN =		{urn:nbn:de:0030-drops-211164},
  doi =		{10.4230/LIPIcs.ESA.2024.45},
  annote =	{Keywords: Distance Sensitive Oracle, Dual Fault Distance Oracle}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.42
Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem

Authors: Dipan Dey and Manoj Gupta

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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.
Cite as

Dipan Dey and Manoj Gupta. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2022.42},
  URN =		{urn:nbn:de:0030-drops-169800},
  doi =		{10.4230/LIPIcs.ESA.2022.42},
  annote =	{Keywords: distance sensitivity oracle, single-source replacement paths}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact