1 citations · 1 across the 2 of their papers we have counts for
5 papers
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 -color…
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 rando…
When MIS and Maximal Matching are Easy in the Congested Clique
Keren Censor-Hillel, Tomer Even, Maxime Flin +1
Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open qu…
Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first general treatment of the coloring of virtual graphs, where the graph to be colored is locally embedded…