Title: Algorithms and Lower Bounds for Distributed Coloring Problems

Speaker: Fabian Kuhn

Place: 32-G531

Time: 1-2:30pm

Date: September 26, 2008

Abstract:
I will give an overview over the current state of the art in distributed
coloring, present some recent new results, and discuss potentially
interesting open problems. In particular, I will show how to obtain local
algorithms for different generalizations of the classical vertex coloring
problem. Based on these results, it is possible to get a new deterministic
distributed algorithm that for any c>=1 computes a c*(Delta+1)-coloring in
O(Delta/c + log*N) time where Delta is the maximum degree and N is the size
of the ID space of the network graph. I will show that this trade-off is
optimal when considering a variant of the distributed coloring problem that
we call the color reduction problem.