Document Open Access Logo

An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, Emo Welzl

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2020.17.pdf
  • Filesize: 463 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Decentralized Algorithm
  • Distributed Computing
  • Graph Coloring
  • Randomized Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].

Cite As Get BibTex

Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.17

Author Details

Daniel Bertschinger
  • Department of Computer Science, ETH Zürich, Switzerland
Johannes Lengler
  • Department of Computer Science, ETH Zürich, Switzerland
Anders Martinsson
  • Department of Computer Science, ETH Zürich, Switzerland
Robert Meier
  • Department of Computer Science, ETH Zürich, Switzerland
Angelika Steger
  • Department of Computer Science, ETH Zürich, Switzerland
Miloš Trujić
  • Department of Computer Science, ETH Zürich, Switzerland
Emo Welzl
  • Department of Computer Science, ETH Zürich, Switzerland

Funding

  • Trujić, Miloš: author was supported by grant no. 200021 169242 of the Swiss National Science Foundation.

References

  1. Apurv Bhartia, Deeparnab Chakrabarty, Krishna Chintalapudi, Lili Qiu, Bozidar Radunovic, and Ramachandran Ramjee. IQ-Hopping: distributed oblivious channel selection for wireless networks. In Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 81-90. ACM, 2016. URL: https://doi.org/10.1145/2942358.2942376.
  2. Deeparnab Chakrabarty and Paul de Supinski. On a Decentralized (Δ + 1)-Graph Coloring Algorithm. In Symposium on Simplicity in Algorithms, pages 91-98. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.13.
  3. Benjamin Doerr and Leslie Ann Goldberg. Adaptive drift analysis. Algorithmica, 65(1):224-250, 2013. URL: https://doi.org/10.1007/s00453-011-9585-3.
  4. Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673-697, 2012. URL: https://doi.org/10.1007/s00453-012-9622-x.
  5. Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996. URL: https://doi.org/10.7146/brics.v3i25.20006.
  6. Jun He and Xin Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1):21-35, 2004. URL: https://doi.org/10.1023/b:naco.0000023417.31393.c7.
  7. Timo Kötzing. Concentration of first hitting times under additive drift. Algorithmica, 75(3):490-506, 2016. URL: https://doi.org/10.1007/s00453-015-0048-0.
  8. Johannes Lengler. Drift analysis. In Benjamin Doerr and Frank Neumann, editors, In: Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 89-131. Springer International Publishing, Cham, 2020. URL: https://doi.org/10.1007/978-3-030-29414-4_2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact