Theory Seminar

Distributed Deterministic Graph Coloring

Michael Elkin

Ben-Gurion University
Friday, September 16, 2011
10:30am - 11:30am
Beyster Bldg. 3941


About the Event

Consider an undirected unweighted n-vertex graph G = (V,E). All vertices host processors, and the processors communicate with each other over edges of G in discrete rounds. The communication is synchronous, and all vertices wake up simultaneously. Vertices have unique identity numbers. In each round each vertex can send distinct messages to all its neighbors. The running time of an algorithm in this model is the number of rounds of distributed communication in its worst-case execution. In the coloring problem we aim to construct a legal f(Delta)-coloring of G, where Delta is the maximum degree of G, and f() is some function. This is a classical and fundamental problem in Distributed Computing. Recently a significant progress was achieved in the study of this problem. I will overview most recent results on distributed coloring, and main techniques that were used to achieve this results. Many questions are left open, and I will present and discuss them. The talk will be self-contained. The talk is based on a series of papers with Leonid Barenboim that were presented at PODCང, STOCཅ, and PODCཆ.

Additional Information

Contact: Seth Pettie


Sponsor: CSE

Open to: Public