Distributed Algorithms for Planar Networks I: Planar Embedding
Distributed Algorithms for Planar Networks I: Planar Embedding
复制标题
平面网络的分布式算法 I：平面嵌入
DOI：
10.1145/2933057.2933109
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler
中科院分区：
文献类型：
--
作者：
M. Ghaffari;Bernhard Haeupler
本文提出了第一个（非平凡的）分布式平面嵌入算法。我们认为这是为平面网络设计高效分布式算法的更广泛计划中至关重要的第一步。我们在标准分布式模型中工作，其中节点每轮可以向其每个邻居发送 O(log n) 位消息。在具有 n 个节点和直径 D 的平面网络中，我们的确定性平面嵌入算法使用 O(D dot min{log n, D) 轮来计算组合平面嵌入，其中每个节点都知道其在固定平面绘图中的入射边的顺时针顺序。我们的算法的复杂性接近最优，并且与 Omega(D) 的平凡下限最高可达 log n 因子相匹配。在这项工作之前，还没有已知的算法能够胜过 O(n) 的平凡轮复杂度。
This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O(log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O(D dot min{log n, D) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.
改进分布式斯坦纳森林建设
DOI：
10.1145/2611462.2611464
发表时间：
2014
期刊：
Proceedings of the 2014 ACM symposium on Principles of distributed computing
影响因子：
--
作者：
Christoph Lenzen;Boaz Patt-Shamir
通讯作者：
Boaz Patt-Shamir