Brief Announcement: Distributed Single-Source Reachability
Brief Announcement: Distributed Single-Source Reachability
复制标题
简短公告：分布式单源可达性
DOI：
10.1145/2767386.2767444
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Udwani
中科院分区：
文献类型：
--
作者：
M. Ghaffari;R. Udwani
在有向单源可达性问题中，输入是一个有向图G=(V，E)和一个源节点S，目标是确定在G中存在从S到t的有向路径的节点t。最近，Nanongkai[STOC‘14]提出了一个分布式算法，该算法在？(D+√)nd1/2轮中求解该问题，其中D和n分别表示网络的直径和节点数。本文给出了一个算法，它将舍入复杂度略微提高到？(D+√nd1/4)，从而更接近Das Sarma等人的~Ω(D+√n)下界。
In the directed single-source reachability problem, input is a directed graph G=(V, E) and a source node s, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai[STOC'14] presented a distributed algorithm that solves this problem in Õ(D+√nD1/2) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that slightly improves the round complexity to Õ(D+√nD1/4), thus getting closer to the ~Ω(D+√n) lower bound of Das Sarma et al.[STOC'11]