Distributed Graph Coloring: Fundamentals and Recent Developments

by Leonid Barenboim and Michael Elkin

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. A typical symmetry-breaking problem is the problem of graph coloring. Denote...

• Format: Paperback
• Language: English
• ISBN: 3031008812
• ISBN13: 9783031008818
• Release Date: August 2013
• Publisher: Springer
• Length: 157 Pages
• Weight: 0.67 lbs.
• Dimensions: 0.4" x 7.5" x 9.3"