1 citations · 1 across the 4 of their papers we have counts for
5 papers · 1 filter
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 -…
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…
Vertex Coloring in Communication
Maxime Flin, Parth Mittal
We study the communication complexity of vertex coloring, where the edges of an -vertex graph of maximum degree are partitioned between two players. We provide a…