Distributed Graph Coloring : Fundamentals and Recent Developments
Leonid Barenboim, Michael Elkin
Bok Engelsk 2013 · Electronic books.
| Annen tittel | |
|---|---|
| Utgitt | San Rafael, Calif. : Morgan & Claypool , c2013
|
| Omfang | xiii, 155 s. : ill
|
| Opplysninger | Description based upon print version of record.. - Acknowledgments; Introduction; Basics of Graph Theory; Graphs with Large Girth and Large Chromatic Number; Planar Graphs; Arboricity; Nash-Williams Theorem; Degeneracy and Arboricity; Defective Coloring; Edge-Coloring and Matchings; Basic Distributed Graph Coloring Algorithns; The Distirubuted Message-Passing LOCAL Model; Basic Color Reduction; Orientations; The Algorithm of Cole and Vishkin; Extensions to Graphs with Bounded Maximum Degree; An Improved Coloring Algorithm for Graphs with Bounded Maximum Degree; A Faster (+ 1)-Coloring. - Edge-Coloring and Maximal MatchingEdge-Coloring and Maximal Matching using Forest-Decomposition; Edge-Coloring Using Bounded Neighborhood Independence; Network Decompositions; Applications of Network Decompositions; Ruling Sets and Forests; Constructing Network Decompositions; Introduction to Distributed Randomized Algorithms; Simple Algorithms; A Faster O-Coloring Algorithm; Randomized MIS; A High-Level Description; Procedure Decide; Randomized Maximal Matching; Graphs with Bounded Arboricity; Conclusion and Open Questions; Problems that can be Solved in Polylogarithmic Time. - Kuhn-Wattenhofer Color Reduction Technique and its ApplicationsA Reduction from (+ 1)-coloring to MIS; Linial's Algorithm; Lower Bounds; Coloring Unoriented Trees; The First Proof; The Second Proof; Coloring the n-path P_n; Forest-Decomposition Algorithms and Applications; H-Partition; An O(a)-coloring; Faster Coloring; MIS Algorithms; Defective Coloring; Employing Defective Coloring for Computing Legal Coloring; Defective Coloring Algorithms; Procedure Refine; Procedure Defective-Color; Arbdefective Coloring; Small Arboricity Decomposition; Efficient Coloring Algorithms. - Problems that can be Solved in (Sub)linear in TimeAlgorithms for Restricted Graph Families; Randomized Algorithms; Bibliography; Authors' Biographies. - 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.
|
| Emner | |
| Sjanger | |
| Dewey | |
| ISBN | 9781627050180
|
