Distributed Weighted All Pairs Shortest Paths Through Pipelining
Distributed Weighted All Pairs Shortest Paths Through Pipelining
复制标题
通过流水线的分布式加权所有对最短路径
DOI：
10.1109/ipdps.2019.00014
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
U. Agarwal;V. Ramachandran
给出了具有中等非负整数权的n结点图拥塞模型中所有对最短路径(APSP)分布式计算的新结果。我们的方法可以处理零权边，这是分布式APSP算法的难点。目前在拥塞模型中处理零权边的最佳确定性分布式算法是Agarwal等人的(n^3/2)轮算法。[ARKP18]这适用于任意边权重。我们的新确定性算法在非负整数边权至多W的图中运行在？(W^1/4⋅n^5/4)轮中，在？(n⋅Δ^1/3)轮中最短路径距离至多Δ。这些算法建立在我们为这个问题提出的一种新的流水线算法之上，该算法最多运行2n√Δ+2n轮。此外，我们还证明了我们结果中的技术简化了[HNS17，ARKP18]中针对非负边权重的早期APSP算法中的一些过程。我们还给出了计算来自k个给定源的h跳最短路径的新结果，并给出了具有非负Polyn(N)整数权的图的(n/ε^2)轮确定的$(1+ε)近似算法，改进了[Nanongkai14，LP15]中仅适用于正整数权的结果。
We present new results for the distributed computation of all pairs shortest paths (APSP) in the CONGEST model in an n-node graph with moderate non-negative integer weights. Our methods can handle zero-weight edges which are known to present difficulties for distributed APSP algorithms. The current best deterministic distributed algorithm in the CONGEST model that handles zero weight edges is the Õ(n^3/2)-round algorithm of Agarwal et al. [ARKP18] that works for arbitrary edge weights. Our new deterministic algorithms run in Õ(W^1/4⋅ n^5/4) rounds in graphs with non-negative integer edge-weight at most W, and in Õ(n ⋅ Δ^1/3) rounds for shortest path distances at most Δ. These algorithms are built on top of a new pipelined algorithm we present for this problem that runs in at most 2n √Δ + 2n rounds. Additionally, we show that the techniques in our results simplify some of the procedures in the earlier APSP algorithms for non-negative edge weights in [HNS17, ARKP18]. We also present new results for computing h-hop shortest paths from k given sources, and we present an Õ(n/ε^2)-round deterministic $(1+ε) approximation algorithm for graphs with non-negative poly(n) integer weights, improving results in [Nanongkai14, LP15] that hold only for positive integer weights.