Search Results

Documents authored by Flin, Maxime

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.79
Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries

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

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the problem of maintaining a proper (Δ + 1)-vertex coloring in a graph on n-vertices and maximum degree Δ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time Õ(n^{2/3}) against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent Õ(n^{8/9})-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic (Δ+1)-coloring algorithms. The main improvements are on the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms.
Cite as

Maxime Flin and Magnús M. Halldórsson. Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 79:1-79:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{flin_et_al:LIPIcs.ICALP.2025.79,
  author =	{Flin, Maxime and Halld\'{o}rsson, Magn\'{u}s M.},
  title =	{{Faster Dynamic (\Delta+1)-Coloring Against Adaptive Adversaries}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{79:1--79:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.79},
  URN =		{urn:nbn:de:0030-drops-234560},
  doi =		{10.4230/LIPIcs.ICALP.2025.79},
  annote =	{Keywords: Dynamic Graph Algorithms, Coloring}
}
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}
}
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