DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.24

Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual Graphs

Authors: Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

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 linearly 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⁴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.

Cite as

Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin. Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual Graphs. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{flin_et_al:LIPIcs.DISC.2024.24,
  author =	{Flin, Maxime and Halld\'{o}rsson, Magn\'{u}s M. and Nolin, Alexandre},
  title =	{{Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual Graphs}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{24:1--24:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.24},
  URN =		{urn:nbn:de:0030-drops-212502},
  doi =		{10.4230/LIPIcs.DISC.2024.24},
  annote =	{Keywords: Graph Coloring, Distributed Algorithms, Virtual Graphs, Congestion, Dilation}
}

Document

DOI: 10.4230/LIPIcs.DISC.2023.19

Fast Coloring Despite Congested Relays

Authors: Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

We provide a O(log⁶ log n)-round randomized algorithm for distance-2 coloring in CONGEST with Δ²+1 colors. For Δ≫polylog n, this improves exponentially on the O(logΔ+polylog log n) algorithm of [Halldórsson, Kuhn, Maus, Nolin, DISC'20].

Cite as

Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin. Fast Coloring Despite Congested Relays. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{flin_et_al:LIPIcs.DISC.2023.19,
  author =	{Flin, Maxime and Halld\'{o}rsson, Magn\'{u}s M. and Nolin, Alexandre},
  title =	{{Fast Coloring Despite Congested Relays}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.19},
  URN =		{urn:nbn:de:0030-drops-191453},
  doi =		{10.4230/LIPIcs.DISC.2023.19},
  annote =	{Keywords: CONGEST model, distributed graph coloring, power graphs}
}

Search Results

Documents authored by Flin, Maxime

Decentralized Distributed Graph Coloring II: Degree+1-Coloring Virtual Graphs

Abstract

Cite as

Fast Coloring Despite Congested Relays

Abstract

Cite as

Thanks for your feedback!

Could not send message