Efficient Deterministic Distributed Coloring with Small Bandwidth
Efficient Deterministic Distributed Coloring with Small Bandwidth
复制标题
小带宽的高效确定性分布式着色
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yannic Maus
中科院分区：
文献类型：
--
作者：
P. Bamberger;F. Kuhn;Yannic Maus
我们证明了在CONGEST模型中（度+ 1）-列表着色问题可以在O（D·log n·log2 Δ）轮中确定性地解决，其中D为图的直径，n为节点数，Δ为最大度。使用rozhokov和Ghaffari[49]最近的多对数时间确定性网络分解算法，这意味着（Δ + 1）-着色和（度+ 1）-列表着色问题的第一个有效（即多对数n-时间）确定性CONGEST算法。以前最著名的算法需要[EQUATION]轮，并且不是基于网络分解。我们的技术还导致了拥挤团和大规模并行计算（MPC）模型的确定性（度+ 1）列表着色算法。对于拥塞团，我们获得了一个时间复杂度为O（log Δ·log log Δ）的算法，对于MPC模型，我们获得了线性存储系统的周期复杂度为O（log2 Δ）和亚线性存储系统的周期复杂度为O（log2 Δ + log n）的算法。
We show that the (degree + 1)-list coloring problem can be solved deterministically in O(D · log n · log2 Δ) rounds in the CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [49], this implies the first efficient (i.e., poly log n-time) deterministic CONGEST algorithm for the (Δ + 1)-coloring and the (degree + 1)-list coloring problem. Previously the best known algorithm required [EQUATION] rounds and was not based on network decompositions. Our techniques also lead to deterministic (degree + 1)-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity O(log Δ · log log Δ), for the MPC model, we obtain algorithms with round complexity O(log2 Δ) for the linear-memory regime and O(log2 Δ + log n) for the sublinear memory regime.