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
Outline
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.
Syllabys
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.
Literature
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.
Projects
-
(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
|