8 papers
Distributed Quantum Algorithms Cannot Color Cycles with Probability 1
Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois +3
We prove that any distributed quantum algorithm that finds a -coloring with probability in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)…
Beyond Brooks: -Coloring in Semi-Streaming
Maxime Flin, Magnús M. Halldórsson
Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree without -cliques are -colorable. We design a one-pass semi-streaming algorithm for…
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Maxime Flin, Magnús M. Halldórsson, Manuel Jakob +1
For any , let be the maximum integer such that . We give a distributed \LOCAL algorithm that, given an integer , computes a valid -…
2-Coloring Cycles in One Round
Maxime Flin, Alesya Raevskaya, Ronja Stimpert +2
We show that there is a one-round randomized distributed algorithm that can 2-color cycles such that the expected fraction of monochromatic edges is less than 0.24118. We also show…
Faster Dynamic -Coloring Against Adaptive Adversaries
Maxime Flin, Magnús M. Halldórsson
We consider the problem of maintaining a proper -vertex coloring in a graph on -vertices and maximum degree undergoing edge insertions and deletions. We give a ran…
Decentralized Distributed Graph Coloring: Cluster Graphs
Maxime Flin, Magnus M. Halldorsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the unde…