000			04944nam a22005295i 4500
001			978-3-031-02009-4
003			DE-He213
005			20240730164237.0
007			cr nn 008mamaa
008			220601s2013 sz | s |||| 0|eng d
020			_a9783031020094 _9978-3-031-02009-4
024	7		_a10.1007/978-3-031-02009-4 _2doi
050		4	_aQA75.5-76.95
072		7	_aUY _2bicssc
072		7	_aCOM000000 _2bisacsh
072		7	_aUY _2thema
082	0	4	_a004 _223
100	1		_aBarenboim, Leonid. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut _983248
245	1	0	_aDistributed Graph Coloring _h[electronic resource] : _bFundamentals and Recent Developments / _cby Leonid Barenboim, Michael Elkin.
250			_a1st ed. 2013.
264		1	_aCham : _bSpringer International Publishing : _bImprint: Springer, _c2013.
300			_aXIII, 157 p. _bonline resource.
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
347			_atext file _bPDF _2rda
490	1		_aSynthesis Lectures on Distributed Computing Theory, _x2155-1634
505	0		_aAcknowledgments -- 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			_aThe 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.
650		0	_aComputer science. _99832
650		0	_aCoding theory. _94154
650		0	_aInformation theory. _914256
650		0	_aData structures (Computer science). _98188
650	1	4	_aComputer Science. _99832
650	2	4	_aCoding and Information Theory. _983251
650	2	4	_aData Structures and Information Theory. _931923
700	1		_aElkin, Michael. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut _983252
710	2		_aSpringerLink (Online service) _983253
773	0		_tSpringer Nature eBook
776	0	8	_iPrinted edition: _z9783031008818
776	0	8	_iPrinted edition: _z9783031031373
830		0	_aSynthesis Lectures on Distributed Computing Theory, _x2155-1634 _983254
856	4	0	_uhttps://doi.org/10.1007/978-3-031-02009-4
912			_aZDB-2-SXSC
942			_cEBK
999			_c85475 _d85475