Mini-Project on Distributed Graph Coloring and Channel Allocation


Class number: 202-1-4071

Schedule: Sunday 16:00-18:00

Bldng 28, Auditorium 107

Office Hours: Sun. 14:00-16:00

Bldng 37, Auditorium 217


The aim of this mini-project is to familiarize students with the research in the area. The students will be required to read a paper or two on this subject, to implement an algorithm described in this paper, and to experiment with this algorithm.

General information

There will be one lecture on Sun., 16:00-18:00, Oct. 20, in Building 32, Hall 210. On this lecture the students will be introduced to the area, and will be told about the papers they can choose. Within three weeks after the beginning of the semester, the students are supposed to choose a paper, and to inform the teacher of their choice. The work can be done in pairs.

From that point on, every three weeks each team should contact the teacher and set an appointment, on which the progress of the team will be evaluated. These meetings will also be used for consulting the teacher concerning the problems that arose during the research.

On the last meeting the students will present their final project. This last meeting should take place before the end of the examination period of the autumn semester.

The grade will be composed from: 60% evaluation of the final project, and 40% evaluation of the progress of the pair throughout the semester.

All the correspondence between the students and the teacher should be conducted through email; phone calls should be used only for very urgent affairs, or if the teacher failed to answer student's email within a period of one week (hopefully, this won't happen).

Projects' reports should be written in English.


The focus in this mini-project will be on distributed algorithms for coloring graphs, and other symmetry-breaking problems, including computing Maximal Independent Set and Maximal Matching. Algorithms for these problems are widely used as subroutines for numerous other distributed algorithms. Therefore, improving algorithms for these problems is of large practical importance. Indeed, this research area was very active in recent years. Morever, these problems seem to encapsulate many important aspects of Distributed Computing. Thus, by studying these algorithms the students will get familiarized with a large magnitude of techniques used elsewhere in the area of Distributed Algorithms.


Most of the material needed for this course can be found in a monograph Distributed Graph Coloring: Fundamentals and Recent Developments, authored by L. Barenboim and myself.


  • (Delta+1)-coloring in O(Delta^2) + log-star n time and (3^Delta)-coloring in log-star n + O(1) time.
    Chapter 7 of my monograph.
    This project includes extensive experimentation.
  • O(a)-coloring in O(a*log n) time. (Chapter 5)
    O(a^2*q)-coloring in time O(log n/log q + a *sqrt{q}) time, for a parameter q.
  • Kuhn-Wattenhofer's Algorithm:
    (Delta+1)-coloring in O(Delta * log Delta) + log-star n time.
    (To avoid implementing Linial's algorithm which is used within Kuhn-Wattenhofer's algorithm, one can implement here (3^Delta)-coloring in log-star n + O(1) time, and then get (Delta+1)-coloring using Kuhn-Wattenhofer's routine within O(Delta^2 + log-star n) time.)
  • Linial's algorithm + Defective Coloring (Ch. 3.10 and Ch. 6, respectively).
    (Delta+1)-coloring in O(Delta) + log-star n time.
  • Arbdefective Coloring - Ch. 7.
  • Edge-Coloring and Maximal Matching (Ch. 8).
  • Network Decomposition (Awerbuch-Goldberg-Luby-Plotkin's algorithm, Ch. 9)
  • Randomized O(Delta)-coloring algorithm that requires O(sqrt{log n}) time.
    (Chapter 10.1-10.2)
    One possibility here is to implement (Delta+1)-coloring and (2*Delta)-coloring in O(log n) time, described in the same chapters.


Requirements for the Mini-Project Report

  • An email letter specifying the requirements,

An outlook letter - opens only from Windows