Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Distributed graph coloring : fundamentals and recent developments
Barenboim L., Elkin M., Morgan&Claypool Publishers, San Rafael, CA, 2013. 172 pp. Type: Book (978-1-627050-18-0)
Date Reviewed: Jul 21 2014

Distributed computing has been an active area of research for a few decades now; we have witnessed significant advances in the principles of distributed computing and the design and analysis of distributed algorithms. Now is the right time for the publication of monographs focused on advances in specific areas of distributed computing. This book is a welcome addition to such a series. It is mainly concerned with two problems: graph coloring and maximal independent sets. These problems are called symmetry breaking problems.

Chapter 1 gives a brief introduction to the message-processing model of distributed computing. All of the algorithms discussed in this book use this model. Also, all of the algorithms considered are synchronous algorithms. Chapter 2 covers several basic results in graph coloring that will be of interest to the discussions in later chapters.

In chapter 3, the authors discuss several distributed graph coloring algorithms. The focus is on Δ+1 coloring. Here Δ is the maximum degree in the graph. First, a fundamental color reduction technique is presented. This enables one to reduce a given coloring to Δ+1 coloring in a certain number of rounds. The other main topics covered include the Cole-Vishkin algorithm for three-coloring oriented trees; extensions to coloring graphs with bounded maximum degree; further extension by Goldberg, Plotkin, and Shannon to Δ+1 coloring of an n-vertex graph in O2) + log* n time; a new color reduction technique more efficient than the one presented earlier in this chapter; and Linial’s algorithm for O2) coloring in log* n + O(1) rounds. Chapter 4 discusses certain lower bound results.

The authors develop a procedure to decompose a graph into a certain number (a function of arboricity denoted by a) of forests in chapter 5. An algorithm that uses this decomposition for 3O(a) coloring with running time O(log n) time is then presented. The issue of tradeoff between the number of colors and the number of rounds (equivalently, time) is then considered. The authors provide an algorithm to achieve O(a) coloring in O(a log n). Extensions to maximum independent set (MIS) constructions are also given.

Defective coloring algorithms that lead to a Δ+1 coloring of an n-vertex graph in O(Δ) + log* n time are covered in chapter 6. Chapter 7 introduces arbdefective coloring, which partitions a graph into subgraphs of bounded arboricity. Using this, the authors present a result that answers in the affirmative the question, raised by Linial, of whether one can determine in polylogarithmic time a coloring with significantly fewer than Δ2 colors.

From the vertex coloring of the line graph of a graph G, one can get an edge coloring of G. So all vertex coloring algorithms discussed thus far can be used for computing edge coloring. Combining forest decomposition with the Cole-Vishkin three-vertex coloring algorithm for oriented trees, chapter 8 presents Panconesi and Rizzi’s 2Δ-1 coloring algorithm for general graphs that runs in O(Δ) + log* n time. The authors’ work on edge coloring for graphs with bounded neighborhood independence is then discussed. Since the line graph of a graph has neighborhood independence bounded by 2, one can get an O1+e) edge coloring algorithm that runs in O(log* n log Δ) time.

Chapter 9 introduces the network decomposition technique originally invented by Awerbuch, Goldberg, Luby, and Plotkin for solving symmetry breaking problems. The main result is that, by using network decomposition, one can get a distributed maximal independent set (MIS) and Δ+1 coloring of time complexity 2O(√log n), a result due to Panconesi and Srinivasan.

Chapter 10 gives an introduction to distributed randomized algorithms for MIS and vertex coloring problems. An algorithm of complexity O(log n) that achieves a Δ+1 coloring with high probability is discussed. Also, it is shown that O(Δ) coloring can be achieved in O (√log n) time with probability 1-1/nc for an arbitrarily large constant c. Chapter 11 concludes with some open problems.

Two minor comments: an introductory discussion of symmetry breaking and what it is all about is absent, as is the context or a scenario in which one encounters the need for synchronous distributed algorithms for the coloring problem.

The authors have succeeded in their goal of reporting most of the advances in distributed graph coloring that have occurred since the publication of Peleg’s book [1]. The writing style is very good, smoothly transitioning from one development to the next. The book is suitable for an advanced course in distributed algorithms for students in theoretical computer science. Also, portions of the book can be used to supplement a course in advanced graph theory and algorithms.

Reviewer:  Krishnaiyan Thulasiraman Review #: CR142531 (1410-0825)
1) Peleg, D. Distributed computing: a locality-sensitive approach. SIAM, Philadelphia, PA, 2000.
Bookmark and Share
  Reviewer Selected
 
 
Graph Theory (G.2.2 )
 
 
Distributed Data Structures (E.1 ... )
 
 
Models Of Computation (F.1.1 )
 
 
Data Structures (E.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy