Distributed Graph Coloring

Book description

The objective of our monograph is to cover the developments on the theoretical foundations of distributed symmetry breaking in the message-passing model. We hope that our monograph will stimulate further progress in this exciting area.

Table of contents

  1. Acknowledgments
  2. Introduction (1/2)
  3. Introduction (2/2)
  4. Basics of Graph Theory
    1. Graphs with Large Girth and Large Chromatic Number
    2. Planar Graphs
    3. Arboricity
      1. Nash-Williams Theorem
      2. Degeneracy and Arboricity
    4. Defective Coloring
    5. Edge-Coloring and Matchings
  5. Basic Distributed Graph Coloring Algorithns
    1. The Distirubuted Message-Passing LOCAL Model
    2. Basic Color Reduction
    3. Orientations
    4. The Algorithm of Cole and Vishkin
    5. Extensions to Graphs with Bounded Maximum Degree
    6. An Improved Coloring Algorithm for Graphs with Bounded Maximum Degree
    7. A Faster (+ 1)-Coloring
    8. Kuhn-Wattenhofer Color Reduction Technique and its Applications
    9. A Reduction from (+ 1)-coloring to MIS
    10. Linial's Algorithm (1/2)
    11. Linial's Algorithm (2/2)
  6. Lower Bounds
    1. Coloring Unoriented Trees
      1. The First Proof
      2. The Second Proof
    2. Coloring the n-path P_n
  7. Forest-Decomposition Algorithms and Applications
    1. H-Partition
    2. An O(a)-coloring
    3. Faster Coloring
    4. MIS Algorithms
  8. Defective Coloring
    1. Employing Defective Coloring for Computing Legal Coloring
    2. Defective Coloring Algorithms
      1. Procedure Refine
      2. Procedure Defective-Color (1/2)
      3. Procedure Defective-Color (2/2)
  9. Arbdefective Coloring
    1. Small Arboricity Decomposition
    2. Efficient Coloring Algorithms (1/2)
    3. Efficient Coloring Algorithms (2/2)
  10. Edge-Coloring and Maximal Matching
    1. Edge-Coloring and Maximal Matching using Forest-Decomposition
    2. Edge-Coloring Using Bounded Neighborhood Independence (1/2)
    3. Edge-Coloring Using Bounded Neighborhood Independence (2/2)
  11. Network Decompositions
    1. Applications of Network Decompositions
    2. Ruling Sets and Forests
    3. Constructing Network Decompositions
  12. Introduction to Distributed Randomized Algorithms
    1. Simple Algorithms
    2. A Faster O()-Coloring Algorithm
    3. Randomized MIS
      1. A High-Level Description
      2. Procedure Decide (1/2)
      3. Procedure Decide (2/2)
    4. Randomized Maximal Matching (1/2)
    5. Randomized Maximal Matching (2/2)
    6. Graphs with Bounded Arboricity (1/2)
    7. Graphs with Bounded Arboricity (2/2)
  13. Conclusion and Open Questions
    1. Problems that can be Solved in Polylogarithmic Time
    2. Problems that can be Solved in (Sub)linear in Time
    3. Algorithms for Restricted Graph Families
    4. Randomized Algorithms
  14. Bibliography (1/2)
  15. Bibliography (2/2)
  16. Authors' Biographies

Product information

  • Title: Distributed Graph Coloring
  • Author(s): Leonid Barenboim, Michael Elkin
  • Release date: July 2013
  • Publisher(s): Morgan & Claypool Publishers
  • ISBN: 9781627050197