Distributed Graph Coloring (Record no. 85475)

000 -LEADER
fixed length control field 04944nam a22005295i 4500
001 - CONTROL NUMBER
control field 978-3-031-02009-4
005 - DATE AND TIME OF LATEST TRANSACTION
control field 20240730164237.0
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION
fixed length control field 220601s2013 sz | s |||| 0|eng d
020 ## - INTERNATIONAL STANDARD BOOK NUMBER
ISBN 9783031020094
-- 978-3-031-02009-4
082 04 - CLASSIFICATION NUMBER
Call Number 004
100 1# - AUTHOR NAME
Author Barenboim, Leonid.
245 10 - TITLE STATEMENT
Title Distributed Graph Coloring
Sub Title Fundamentals and Recent Developments /
250 ## - EDITION STATEMENT
Edition statement 1st ed. 2013.
300 ## - PHYSICAL DESCRIPTION
Number of Pages XIII, 157 p.
490 1# - SERIES STATEMENT
Series statement Synthesis Lectures on Distributed Computing Theory,
505 0# - FORMATTED CONTENTS NOTE
Remark 2 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.
520 ## - SUMMARY, ETC.
Summary, etc 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 by ? the maximum degree of G. While coloring G with ? + 1 colors is trivial in the centralized setting, the problem becomes much more challenging in the distributed one. One can also compromise on the number of colors, if this allows for more efficient algorithms. Other typical symmetry-breaking problems are the problems of computing a maximal independent set (MIS) and a maximal matching (MM). The study of these problems dates back to the very early days of distributed computing. The founding fathers of distributed computing laid firm foundations for the area of distributed symmetry breaking already in the eighties. In particular, they showed that all these problems can be solved in randomized logarithmic time. Also, Linial showed that an O(?2)-coloring can be solved very efficiently deterministically. However, fundamental questions were left open for decades. In particular, it is not known if the MIS or the (? + 1)-coloring can be solved in deterministic polylogarithmic time. Moreover, until recently it was not known if in deterministic polylogarithmic time one can color a graph with significantly fewer than ?2 colors. Additionally, it was open (and still open to some extent) if one can have sublogarithmic randomized algorithms for the symmetry breaking problems. Recently, significant progress was achieved in the study of these questions. More efficient deterministic and randomized (? + 1)-coloring algorithms were achieved. Deterministic ?1 + o(1)-coloring algorithms with polylogarithmic running time were devised. Improved (and often sublogarithmic-time) randomized algorithms were devised. Drastically improved lower bounds were given. Wide families of graphs in which these problems are solvable much faster than on general graphs were identified. The objective of our monograph is to cover most of these developments, and as a result to provide a treatise on theoretical foundations of distributed symmetry breaking in the message-passing model. We hope that our monograph will stimulate further progress in this exciting area.
700 1# - AUTHOR 2
Author 2 Elkin, Michael.
856 40 - ELECTRONIC LOCATION AND ACCESS
Uniform Resource Identifier https://doi.org/10.1007/978-3-031-02009-4
942 ## - ADDED ENTRY ELEMENTS (KOHA)
Koha item type eBooks
264 #1 -
-- Cham :
-- Springer International Publishing :
-- Imprint: Springer,
-- 2013.
336 ## -
-- text
-- txt
-- rdacontent
337 ## -
-- computer
-- c
-- rdamedia
338 ## -
-- online resource
-- cr
-- rdacarrier
347 ## -
-- text file
-- PDF
-- rda
650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Computer science.
650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Coding theory.
650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Information theory.
650 #0 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Data structures (Computer science).
650 14 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Computer Science.
650 24 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Coding and Information Theory.
650 24 - SUBJECT ADDED ENTRY--SUBJECT 1
-- Data Structures and Information Theory.
830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE
-- 2155-1634
912 ## -
-- ZDB-2-SXSC

No items available.