Distributed Symmetry-Breaking Algorithms for Congested Cliques
Distributed Symmetry-Breaking Algorithms for Congested Cliques
复制标题
针对拥塞派系的分布式对称破缺算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Khazanov
中科院分区：
文献类型：
--
作者：
Leonid Barenboim;V. Khazanov
拥塞集团是一种针对带宽受限的单跳网络的分布式计算模型，近年来得到了广泛的研究。它通过一个$n$-顶点图来模拟一个网络，在这个图中，任何一对顶点都可以通过在每一轮中传输$O（log n）$比特来相互通信。在这一背景下，人们已经研究了各种各样的问题，但其中一些最著名的结果是针对一般网络的。在本文中，我们设计了显着改进的算法，如森林分解，顶点着色，和最大独立集的各种破坏问题。
我们分析我们的算法的运行时间作为一个函数的荫度$a$的一个集团子图，作为输入。我们的算法是特别有效的树，平面图，图与常亏格，和许多其他的图，有界荫度，但无界的大小。我们得到了$O（log a）$时间的$O（a）$-森林分解算法，改进了以前已知的$O（log n）$时间，$O在$O（log^* n）$时间内的（a^{2 + n}）$-染色，改进了$O（log n）$时间算法，$O（a）$-染色在$O（a^{n}）$-时间，改进了几个先前的算法，和一个最大独立集算法与$O（sqrt a）$的时间，提高至少二次方后，国家的最先进的小和中等值的$a$。
这些结果是使用几种技术实现的。首先，我们在$O（log a）$轮内生成一个森林分解，它具有一个称为{$H$-partition}的有用结构。在一般的图中，这种结构需要$Theta（log n）$时间，但在拥挤的集团中，我们能够更快地计算它。我们采用这种结构结合分区技术，使我们能够有效地解决各种破坏性的问题。
The {Congested Clique} is a distributed-computing model for single-hop networks with restricted bandwidth that has been very intensively studied recently. It models a network by an $n$-vertex graph in which any pair of vertices can communicate one with another by transmitting $O(log n )$ bits in each round. Various problems have been studied in this setting, but for some of them the best-known results are those for general networks. In this paper we devise significantly improved algorithms for various symmetry-breaking problems, such as forests-decompositions, vertex-colorings, and maximal independent set.
We analyze the running time of our algorithms as a function of the arboricity $a$ of a clique subgraph that is given as input. Our algorithms are especially efficient in Trees, planar graphs, graphs with constant genus, and many other graphs that have bounded arboricity, but unbounded size. We obtain $O(a)$-forest-decomposition algorithm with $O(log a)$ time that improves the previously-known $O(log n)$ time, $O(a^{2 + epsilon})$-coloring in $O(log^* n)$ time that improves upon an $O(log n)$-time algorithm, $O(a)$-coloring in $O(a^{epsilon})$-time that improves upon several previous algorithms, and a maximal independent set algorithm with $O(sqrt a)$ time that improves at least quadratically upon the state-of-the-art for small and moderate values of $a$.
Those results are achieved using several techniques. First, we produce a forest decomposition with a helpful structure called {$H$-partition} within $O(log a)$ rounds. In general graphs this structure requires $Theta(log n)$ time, but in Congested Cliques we are able to compute it faster. We employ this structure in conjunction with partitioning techniques that allow us to solve various symmetry-breaking problems efficiently.