Distributed symmetry-breaking algorithms for congested cliques

Leonid Barenboim, Victor Khazanov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


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. For other problems, the results for Congested Cliques are better than on general networks, but still incur significant dependency on the number of vertices n. Hence the performance of these algorithms may become poor on large cliques, even though their diameter is just 1. 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. The arboricity is always smaller than the number of vertices n in the subgraph, and for many families of graphs it is significantly smaller. In particular, trees, planar graphs, graphs with constant genus, and many other graphs 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(a2+ε)-coloring in O(log*n) time that improves upon an O(log n)-time algorithm, O(a)-coloring in (aε)-time that improves upon several previous algorithms, and a maximal independent set algorithm with O(√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 Θ(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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفComputer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings
المحررونVladimir V. Podolskii, Fedor V. Fomin
ناشرSpringer Verlag
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)9783319905297
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2018
الحدث13th International Computer Science Symposium in Russia, CSR 2018 - Moscow, روسيا
المدة: ٦ يونيو ٢٠١٨١٠ يونيو ٢٠١٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت10846 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference13th International Computer Science Symposium in Russia, CSR 2018

ملاحظة ببليوغرافية

Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.


أدرس بدقة موضوعات البحث “Distributed symmetry-breaking algorithms for congested cliques'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا