论文标题
替换路径和相关问题的接近最佳范围
Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
论文作者
论文摘要
我们在圆形复杂性的替换路径（RPATH），最小重量周期（MWC）和所有最短周期（ANSC）的所有节点的圆形复杂度上介绍了几个结果。我们研究了加权和未加权的定向图和无向图中的这些基本问题。我们的许多结果对于多聚磁因素是最佳选择：对于$ n $ node图$ g $，如果指示和加权$ g $，我们在线性下限和上限附近建立，并且计算MWC和ANSC（如果$ g $）是加权，定向或无向;接近$ \ sqrt {n} $下限和上限，用于无方向的加权rPath；和$θ（d）$限制为未指向的未加权rPATH。我们还为这些问题的近似版本提供了下限和上限，尤其是$（2-（1/g））$ - 近似算法，用于未转向的未向内MWC，该算法以$ \ tilde {o}（\ sqrt {n} $ \ tilde {o}（\ sqrt {ng}+d）$ rounds，其中$ g $是MWC长度。我们提出了针对定向加权的RPATH的$（1+ε）$ - 近似算法，该算法超过线性下限以获得精确的RPATH。
We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, both weighted and unweighted. Many of our results are optimal to within a polylog factor: For an $n$-node graph $G$ we establish near linear lower and upper bounds for computing RPaths if $G$ is directed and weighted, and for computing MWC and ANSC if $G$ is weighted, directed or undirected; near $\sqrt{n}$ lower and upper bounds for undirected weighted RPaths; and $Θ(D)$ bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation versions of these problems, notably a $(2-(1/g))$-approximation algorithm for undirected unweighted MWC that runs in $\tilde{O}(\sqrt{n}+D)$ rounds, improving on the previous best bound of $\tilde{O}(\sqrt{ng}+D)$ rounds, where $g$ is the MWC length. We present a $(1+ε)$-approximation algorithm for directed weighted RPaths, which beats the linear lower bound for exact RPaths.
