Report
Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
| العنوان: | Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs |
|---|---|
| المؤلفون: | Flin, Maxime, Halldórsson, Magnús M., Nolin, Alexandre |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms |
| الوصف: | Graph coloring is fundamental to distributed computing. We give the first general treatment of the coloring of virtual graphs, where the graph $H$ to be colored is locally embedded within the communication graph $G$. Besides generalizing classical distributed graph coloring (where $H=G$), this captures other previously studied settings, including cluster graphs and power graphs. We find that the complexity of coloring a virtual graph depends on the edge congestion of its embedding. The main question of interest is how fast we can color virtual graphs of constant congestion. We find that, surprisingly, these graphs can be colored nearly as fast as ordinary graphs. Namely, we give a $O(\log^4\log n)$-round algorithm for the deg+1-coloring problem, where each node is assigned more colors than its degree. This can be viewed as a case where a distributed graph problem can be solved even when the operation of each node is decentralized. Comment: 56 pages. To appear in proceedings of DISC 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2408.11041 |
| رقم الانضمام: | edsarx.2408.11041 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |