论文标题
有效计算全对最短路径的有效参数化算法
Efficient parameterized algorithms for computing all-pairs shortest paths
论文作者
论文摘要
最短路径计算全对是许多应用程序的基本且备受研究的问题。不幸的是，尽管进行了激烈的研究，但它仍然没有明显更快的算法比$ \ Mathcal {o}（n^3）$ time算法由于Floyd和Warshall（1962）。如果可以使用快速矩阵乘法，则存在顶点加权版本的算法更快的算法。 Yuster（Soda 2009）给出了一种随时间运行的算法，$ \ Mathcal {O}（N^{2.842}）$，但没有众所周知的组合算法。 在有效的参数化算法（或“ p”中的“ fpt”）的最新框架中，我们研究了图参数的影响，即Clique-width（$ CW $）和模块化宽度（$ MW $）对算法的运行时间用于求解全与最短路径的算法。我们在非阴性顶点加权图上获得了有效的（和组合）参数化算法，$ \ MATHCAL {O}（cw^2n^2）$，resp。 $ \ mathcal {o}（mw^2n + n^2）$。如果允许快速矩阵乘法，则可以使用Yuster的算法将后者改进到$ \ Mathcal {O}（MW^{1.842} N + N^2）$。相对于模块化宽度的算法是自适应的，这意味着运行时间与最佳的未参数化算法匹配参数值$ mw $等于$ n $的最佳无参数化算法，并且它们的表现已经超越了它们，它们的表现已经超过$ mw \ in \ nathcal {o}（o}（o}（n^{n^{1- \ varepsilon}）
Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the $\mathcal{O}(n^3)$ time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time $\mathcal{O}(n^{2.842})$, but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width ($cw$) and modular-width ($mw$) on the running times of algorithms for solving All-Pairs Shortest Paths. We obtain efficient (and combinatorial) parameterized algorithms on non-negative vertex-weighted graphs of times $\mathcal{O}(cw^2n^2)$, resp. $\mathcal{O}(mw^2n + n^2)$. If fast matrix multiplication is allowed then the latter can be improved to $\mathcal{O}(mw^{1.842}n + n^2)$ using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value $mw$ equal to $n$, and they outperform them already for $mw \in \mathcal{O}(n^{1 - \varepsilon})$ for any $\varepsilon > 0$.
