论文标题
接近最佳算法，可容忍距离距离甲骨文和单源替换路径问题
Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
论文作者
论文摘要
在带有源$ s $的图形$ g $中，我们设计了一个距离甲骨文，可以回答以下查询：查询$（s，t，e）$ - 找到从固定源$ s $到任何目标顶点$ t $的最短路径的最短路径长度，同时避免任何边缘$ e $。我们设计了一种确定性算法，该算法在$ \ tilde {o}（m \ sqrt n）$ time中构建了这样的甲骨文。我们的Oracle使用$ \ tilde {o}（n \ sqrt n）$ space，可以回答$ \ tilde {o}（1）$ time中的查询。我们的甲骨文是Bilò等人的作品的改进。 （ESA 2021）在预处理时间中，该时间在$ \ tilde {o}（m \ sqrt n+n^2）中构造了此问题的第一个确定性甲骨文。 使用我们的距离Oracle，我们还解决了{\ em单源替换路径问题}（SSR问题）。 Chechik和Cohen（Soda 2019）设计了一种随机组合算法来解决SSR问题。其算法的运行时间为$ \ tilde {o}（m \ sqrt n + n^2）$。在本文中，我们表明可以在$ \ tilde {o}（m \ sqrt n + | \ mathcal {r} |）$ time中解决SSR问题，其中$ \ Mathcal {r} $是$ G $中SSR问题的输出集。我们的SSR算法是最佳的（最高（最多），因为对于解决此问题的任何组合算法，有条件下限$ω（M \ sqrt n）$。
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 $\tilde{O}(m\sqrt n)$ time. Our oracle uses $\tilde{O}(n\sqrt n)$ space and can answer queries in $\tilde{O}(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 $\tilde{O}(m\sqrt n+n^2)$ time. Using our distance oracle, we also solve the {\em single source replacement path problem} (SSR problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the SSR problem. The running time of their algorithm is $\tilde{O}(m\sqrt n + n^2)$. In this paper, we show that the SSR problem can be solved in $\tilde{O}(m\sqrt n + |\mathcal{R}|)$ time, where $\mathcal{R}$ is the output set of the SSR problem in $G$. Our SSR algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of $Ω(m\sqrt n)$ for any combinatorial algorithm that solves this problem.
