1 citations · 1 across the 10 of their papers we have counts for
6 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…
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…
Coloring Fast with Broadcasts
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We present an -round distributed algorithm for the -coloring problem, where each node broadcasts only one -bit message per round to its neighbors…
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a coloring of the graph, where denotes the maximum degree, it suf…