Showing cs.DCShow all
3 papers · 1 filter
cs.DC2026
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…
cs.DC2025
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…
cs.DC2025
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…