| 书目名称 | Distributed Graph Coloring | | 副标题 | Fundamentals and Rec | | 编辑 | Leonid Barenboim,Michael Elkin | | 视频video | | | 丛书名称 | Synthesis Lectures on Distributed Computing Theory | | 图书封面 |  | | 描述 | 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 tha | | 出版日期 | Book 2013 | | 版次 | 1 | | doi | https://doi.org/10.1007/978-3-031-02009-4 | | isbn_softcover | 978-3-031-00881-8 | | isbn_ebook | 978-3-031-02009-4Series ISSN 2155-1626 Series E-ISSN 2155-1634 | | issn_series | 2155-1626 | | copyright | Springer Nature Switzerland AG 2013 |
The information of publication is updating
|
|
发表于 2025-3-21 16:29:28
