Distributed Planar Reachability in Nearly Optimal Time
Distributed Planar Reachability in Nearly Optimal Time
复制标题
近乎最佳时间的分布式平面可达性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Parter
中科院分区：
文献类型：
--
作者：
M. Parter
我们提出了近最佳的分布式算法的基本可达性问题的平面图。在单源可达性问题中，给定一个n -顶点有向图G =（V，E）和一个源节点s，需要确定G中从s可达的节点子集。我们提出了平面图的第一个分布式可达性算法，该算法在e O（D）轮的近最优时间内运行，其中D是图的无向直径。这提高了复杂性的e O（D 2）轮暗示最近的工作[李和Parter，STOC'19]。我们还考虑了更一般的可达性问题，确定强连通组件（SCC）的图。我们提出了一个e O（D）轮算法，该算法为图中的每个节点计算其在G中的强连通分量的标识符。没有非平凡的上限这个问题（即使在一般的图）已经知道。我们的算法是基于表征平衡循环分隔符之间的结构相互作用。我们表明，分隔符节点之间的可达性关系可以被压缩，由于他们的有向最短路径的Monge类属性。通过将这种结构表征与[Li和Parter，STOC'19]的递归图划分机器相结合来获得算法结果。
We present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the single-source reachability problem given is an n -vertex directed graph G = ( V, E ) and a source node s , it is required to determine the subset of nodes that are reachable from s in G . We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of e O ( D ) rounds, where D is the undirected diameter of the graph. This improves the complexity of e O ( D 2 ) rounds implied by the recent work of [Li and Parter, STOC’19]. We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an e O ( D )-round algorithm that computes for each node in the graph an identifier of its strongly connected component in G . No non-trivial upper bound for this problem (even in general graphs) has been known before. Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Monge-like property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC’19].
登录
查看更多内容
轮次和消息最优分布式图算法
DOI：
10.1145/3212734.3212737
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Wajc, David
通讯作者：
Wajc, David
DOI：
10.1145/3357713.3384310
发表时间：
2020-06
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Amir Abboud;Vincent Cohen-Addad;P. Klein
通讯作者：
Amir Abboud;Vincent Cohen-Addad;P. Klein
少数被排除在外的网络家族承认快速分布式算法
DOI：
10.1145/3212734.3212776
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Li, Jason;Zuzic, Goran
通讯作者：
Zuzic, Goran
几乎线性功和平方根深度的并行可达性
DOI：
10.1109/focs.2019.00098
发表时间：
2019
期刊：
Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Liu, Yang P.;Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron
无需嵌入的低拥塞快捷方式
影响因子：
1.3
作者：
Haeupler, Bernhard;Izumi, Taisuke;Zuzic, Goran
通讯作者：
Zuzic, Goran