Distributed Graph Coloring

Fundamentals and Recent Developments

AvLeonid Barenboim,Michael Elkin

Häftad, Engelska, 2013

Del i serien Synthesis Lectures on Distributed Computing Theory

423 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Beskrivning

The focus of this monograph is on symmetry breaking problems in the message-passing model of distributed computing. A typical symmetry-breaking problem is the problem of graph coloring. Other typical symmetry-breaking problems are the problems of computing a maximal independent set (MIS) and a maximal matching (MM).

Produktinformation

Utgivningsdatum:2013-08-07
Mått:191 x 235 x 16 mm
Vikt:334 g
Format:Häftad
Språk:Engelska
Serie:Synthesis Lectures on Distributed Computing Theory
Antal sidor:157
Förlag:Springer International Publishing AG
ISBN:9783031008818
Originaltitel:Distributed Graph Coloring

Utforska kategorier

Mer om författaren

Michael Elkin received his Ph.D. in Computer Science and Mathemat ics from the Weizmann Institute, Rehovot, Israel, in 2002. He held po sitions in the Institute for Advanced Study in Princeton and in Yale Uni versity, before joining the Ben-Gurion University of the Negev in 2004. He is an Associate Professor in the Computer Science department in the Ben-Gurion University. His main research interests are distributed algorithms, graph algorithms and metric embeddings. Leonid Barenboim performed his Ph.D. research in Computer Science in Ben-Gurion University of the Negev. His research deals with dis tributed algorithms for symmetry-breaking and synchronization. His re search interests also include graph theory, randomized algorithms and approximation algorithms. He served as a lecturer of a course on im plementation of distributed algorithms and a course on object oriented programming. In 2013 he was accepted to the joint research program of Berkeley and I-CORE that deals with the theoryof big data analysis and large-scale networks

Innehållsförteckning

Acknowledgments.- Introduction.- Basics of Graph Theory.- Basic Distributed Graph Coloring Algorithns.- Lower Bounds.- Forest-Decomposition Algorithms and Applications.- Defective Coloring.- Arbdefective Coloring.- Edge-Coloring and Maximal Matching.- Network Decompositions.- Introduction to Distributed Randomized Algorithms.- Conclusion and Open Questions.- Bibliography.- Authors' Biographies.