5 papers
Fast Distributed -Edge Coloring in Bipartite Graphs
Yann Bourreau, Sebastian Brandt, Ananth Narayanan
We show that, on bipartite -vertex graphs in the LOCAL model of distributed computation, -edge coloring can be solved deterministically in rounds for so…
Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality
Yann Bourreau, Filippo Casagrande, Tim Göttlicher +1
We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of around a…
Faster Distributed -Coloring via a Reduction to MIS
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of $\tild…
Optimal Deterministic Rendezvous in Labeled Lines
Yann Bourreau, Ananth Narayanan, Alexandre Nolin
In a rendezvous task, some mobile agents dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with $2…
Faster Distributed -Coloring via Ruling Subgraphs
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
Brooks' theorem states that all connected graphs but odd cycles and cliques can be colored with colors, where is the maximum degree of the graph. Such colorings have been s…