ICS Theory Group

ICS 269, Winter 2001: Theory Seminar

Mar 16 2001:
A presentation of "Fast distributed graph coloring in O(Delta) colors," by Gianluca De Marco and Andrzej Pelc, from SODA 2001.
Speaker: David Goggin, ICS, UC Irvine

We consider the problem of deterministic distributed coloring of an n-vertex graph with maximum degree 'delta', assuming that ev ery vertex knows a priori only its own label and parameters n and 'delta.' The aim is to get a fast algorithm using few colors. Linial showed a vertex-coloring algorithm working in time O(log* n) and using O(Delta^2) colors. We improve both the time and the number of colors simultaneously by showing an algorithm working in time O(log* (n/Delta)) and using O(Delta) colors. This is the first known O(Delta) vertex coloring distributed algorithm which can work faster than in polylogarithmic time.