Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs
Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs
复制标题
简化和统一加权有向图中的替换路径算法
DOI：
10.4230/lipics.icalp.2020.29
复制
发表时间：
2020
影响因子：
1.9
通讯作者：
Moran Nechushtan
中科院分区：
文献类型：
--
作者：
S. Chechik;Moran Nechushtan
在替换路径（RP）问题中，我们得到了一个图形g，并且两个节点s和t之间的最短路径是为每个边缘e∈P找到的本文的第一个结果是从RP问题简单地减少到最短路径上所有节点的最短周期的问题。
使用这种简单的还原，我们将两种不同研究的RP问题变体统一并极为简化了两种艺术解决方案。
在第一个变体（代数）中，我们表明，通过最多在Yuster-Zwick距离Oracle [focs 2005]中使用最多n询问，可以解决给定有向的图形的RP问题，该图在范围内具有整数边缘权重[-m，， M]在O（m n^ω）时间。
在第二个变体（平面）中，我们表明，通过使用klein的算法进行多源最短路径问题（MSSP）[SODA 2005]，可以解决针对有向平面图的RP问题，而O（n log n）时间。
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 O(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.