1 Search Results for "Nechushtan, Moran"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.29
Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs

Authors: Shiri Chechik and Moran Nechushtan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In the replacement paths (RP) problem we are given a graph G and a shortest path P between two nodes s and t . The goal is to find for every edge e ∈ P, a shortest path from s to t that avoids e. The first result of this paper is a simple reduction from the RP problem to the problem of computing shortest cycles for all nodes on a shortest path. Using this simple reduction we unify and extremely simplify two state of the art solutions for two different well-studied variants of the RP problem. In the first variant (algebraic) we show that by using at most n queries to the Yuster-Zwick distance oracle [FOCS 2005], one can solve the the RP problem for a given directed graph with integer edge weights in the range [-M,M] in Õ(M n^ω) time . This improves the running time of the state of the art algorithm of Vassilevska Williams [SODA 2011] by a factor of log⁶n. In the second variant (planar) we show that by using the algorithm of Klein for the multiple-source shortest paths problem (MSSP) [SODA 2005] one can solve the RP problem for directed planar graph with non negative edge weights in O (n log n) time. This matches the state of the art algorithm of Wulff-Nilsen [SODA 2010], but with arguably much simpler algorithm and analysis.
Cite as

Shiri Chechik and Moran Nechushtan. Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chechik_et_al:LIPIcs.ICALP.2020.29,
  author =	{Chechik, Shiri and Nechushtan, Moran},
  title =	{{Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{29:1--29:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.29},
  URN =		{urn:nbn:de:0030-drops-124365},
  doi =		{10.4230/LIPIcs.ICALP.2020.29},
  annote =	{Keywords: Fault tolerance, Distance oracle, Planar graph}
}
  • Refine by Author
  • 1 Chechik, Shiri
  • 1 Nechushtan, Moran

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Distance oracle
  • 1 Fault tolerance
  • 1 Planar graph

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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 Imprint Privacy Contact