Distributed graph coloring [electronic resource] : fundamentals and recent developments
 Responsibility
 Leonid Barenboim and Michael Elkin.
 Imprint
 San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, c2013.
 Physical description
 1 electronic text (xiii, 157 p.).
 Series
 Synthesis digital library of engineering and computer science.
 Synthesis lectures on distributed computing theory #11.
Online
More options
Description
Creators/Contributors
 Author/Creator
 Barenboim, Leonid.
 Contributor
 Elkin, Michael.
Contents/Summary
 Bibliography
 Includes bibliographical references (p. 149155).
 Contents

 Acknowledgments Introduction Basics of Graph Theory Basic Distributed Graph Coloring Algorithns Lower Bounds ForestDecomposition Algorithms and Applications Defective Coloring Arbdefective Coloring EdgeColoring and Maximal Matching Network Decompositions Introduction to Distributed Randomized Algorithms Conclusion and Open Questions Bibliography Authors' Biographies.
 (source: Nielsen Book Data)
 Publisher's summary

The focus of this monograph is on symmetry breaking problems in the messagepassing model of distributed computing. In this model a communication network is represented by a nvertex graph G = (V, E), whose vertices host autonomous processors. The processors communicate over the edges of G in discrete rounds. The goal is to devise algorithms that use as few rounds as possible. A typical symmetrybreaking problem is the problem of graph coloring. Denote by ? the maximum degree of G. While coloring G with ? + 1 colors is trivial in the centralized setting, the problem becomes much more challenging in the distributed one. One can also compromise on the number of colors, if this allows for more efficient algorithms. Other typical symmetrybreaking problems are the problems of computing a maximal independent set (MIS) and a maximal matching (MM). The study of these problems dates back to the very early days of distributed computing. The founding fathers of distributed computing laid firm foundations for the area of distributed symmetry breaking already in the eighties. In particular, they showed that all these problems can be solved in randomized logarithmic time. Also, Linial showed that an O(?2)coloring can be solved very efficiently deterministically. However, fundamental questions were left open for decades. In particular, it is not known if the MIS or the (? + 1)coloring can be solved in deterministic polylogarithmic time. Moreover, until recently it was not known if in deterministic polylogarithmic time one can color a graph with significantly fewer than ?2 colors. Additionally, it was open (and still open to some extent) if one can have sublogarithmic randomized algorithms for the symmetry breaking problems. Recently, significant progress was achieved in the study of these questions. More efficient deterministic and randomized (? + 1)coloring algorithms were achieved. Deterministic ?1 + o(1)coloring algorithms with polylogarithmic running time were devised. Improved (and often sublogarithmictime) randomized algorithms were devised. Drastically improved lower bounds were given. Wide families of graphs in which these problems are solvable much faster than on general graphs were identified. The objective of our monograph is to cover most of these developments, and as a result to provide a treatise on theoretical foundations of distributed symmetry breaking in the messagepassing model. We hope that our monograph will stimulate further progress in this exciting area.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2013
 Series
 Synthesis lectures on distributed computing theory, 21551634 ; #11
 Note
 Part of: Synthesis digital library of engineering and computer science.
 Series from website.
 Access
 Abstract freely available; fulltext restricted to subscribers or individual document purchasers.
 Referenced in
 Compendex
 INSPEC
 Google scholar
 Google book search
 Note
 Also available in print.
 Format
 Mode of access: World Wide Web.
 System requirements: Adobe Acrobat Reader.
 ISBN
 9781627050197 (electronic bk.)
 9781627050180 (pbk.)
 1627050191 (electronic bk.)
 DOI
 10.2200/S00520ED1V01Y201307DCT011