1 citations · 1 across the 2 of their papers we have counts for
3 papers · 1 filter
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…
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…