4 papers · 1 filter
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…
A Fast Deterministic Algorithm for -edge coloring in CONGEST
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
Vizing's theorem states that any graph of maximum degree can be properly edge-colored with colors (which is optimal in general). A recent breakthrough result by Bernshte…
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…
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…