Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 149-155).

1. Introduction --

2. Basics of graph theory -- 2.1 Graphs with large girth and large chromatic number -- 2.2 Planar graphs -- 2.3 Arboricity -- 2.3.1 Nash-Williams theorem -- 2.3.2 Degeneracy and arboricity -- 2.4 Defective coloring -- 2.5 Edge-coloring and matchings --

3. Basic distributed graph coloring algorithms -- 3.1 The distributed message-passing LOCAL model -- 3.2 Basic color reduction -- 3.3 Orientations -- 3.4 The algorithm of Cole and Vishkin -- 3.5 Extensions to graphs with bounded maximum degree -- 3.6 An improved coloring algorithm for graphs with bounded maximum degree -- 3.7 A faster ([delta plus] 1)-coloring -- 3.8 Kuhn-Wattenhofer color reduction technique and its applications -- 3.9 A reduction from ([delta plus] 1)-coloring to MIS -- 3.10 Linial's algorithm --

4. Lower bounds -- 4.1 Coloring unoriented trees -- 4.1.1 The first proof -- 4.1.2 The second proof -- 4.2 Coloring the n-path Pn --

5. Forest-decomposition algorithms and applications -- 5.1 H-partition -- 5.2 An O(a)-coloring -- 5.3 Faster coloring -- 5.4 MIS algorithms --

6. Defective coloring -- 6.1 Employing defective coloring for computing legal coloring -- 6.2 Defective coloring algorithms -- 6.2.1 Procedure refine -- 6.2.2 Procedure defective-color --

7. Arbdefective coloring -- 7.1 Small arboricity decomposition -- 7.2 Efficient coloring algorithms --

8. Edge-coloring and maximal matching -- 8.1 Edge-coloring and maximal matching using forest-decomposition -- 8.2 Edge-coloring using bounded neighborhood independence --

9. Network decompositions -- 9.1 Applications of network decompositions -- 9.2 Ruling sets and forests -- 9.3 Constructing network decompositions --

10. Introduction to distributed randomized algorithms -- 10.1 Simple algorithms -- 10.2 A faster O([delta])-coloring algorithm -- 10.3 Randomized MIS -- 10.3.1 A high-level description -- 10.3.2 Procedure decide -- 10.4 Randomized maximal matching -- 10.5 Graphs with bounded arboricity --

11. Conclusion and open questions -- 11.1 Problems that can be solved in polylogarithmic time -- 11.2 Problems that can be solved in (sub)linear in [delta] time -- 11.3 Algorithms for restricted graph families -- 11.4 Randomized algorithms --

Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

The focus of this monograph is on symmetry breaking problems in the message-passing model of distributed computing. In this model a communication network is represented by a n -vertex 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.

Also available in print.

Title from PDF t.p. (viewed on August 14, 2013).