Distributed Graph Coloring: Fundamentals and Recent Developments (Paperback)

Leonid Barenboim, Michael Elkin

  • 出版商: Morgan & Claypool
  • 出版日期: 2013-07-01
  • 定價: $1,400
  • 售價: 9.0$1,260
  • 語言: 英文
  • 頁數: 172
  • 裝訂: Paperback
  • ISBN: 1627050183
  • ISBN-13: 9781627050180
  • 相關分類: Computer-networks
  • 立即出貨 (庫存=1)

商品描述

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 [delta] the maximum degree of G. While coloring G with [delta]+ 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([delta]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 ([delta] + 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 [delta]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 ([delta] + 1)-coloring algorithms were achieved. Deterministic [delta]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.

Table of Contents: 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

商品描述(中文翻譯)

本專著的重點是討論在分散式計算的消息傳遞模型中的對稱破壞問題。在這個模型中,通信網絡由一個包含n個頂點的圖G = (V,E)表示,其中每個頂點都有自主處理器。處理器在G的邊上進行離散回合的通信。目標是設計使用最少回合的算法。

一個典型的對稱破壞問題是圖著色問題。用[delta]表示G的最大度數。在集中式環境中,使用[delta]+1種顏色對G進行著色是簡單的,但在分散式環境中,這個問題變得更具挑戰性。如果這樣做可以得到更高效的算法,也可以妥協於顏色的數量。其他典型的對稱破壞問題包括計算最大獨立集(MIS)和最大匹配(MM)的問題。對這些問題的研究可以追溯到分散式計算的早期。分散式計算的奠基人在八十年代已經為分散式對稱破壞領域奠定了堅實的基礎。特別是,他們表明所有這些問題都可以在隨機對數時間內解決。此外,Linial還表明可以以O([delta]2)的顏色非常高效地確定性地解決著色問題。

然而,一些基本問題數十年來一直未解。特別是,我們不知道MIS或([delta]+1)-著色是否可以在確定性多對數時間內解決。此外,直到最近我們還不知道在確定性多對數時間內是否可以用遠少於[delta]2種顏色對圖進行著色。此外,對於對稱破壞問題是否可以有次對數隨機算法,一直存在一定程度的開放問題。

最近,在這些問題的研究中取得了重大進展。實現了更高效的確定性和隨機性([delta]+1)-著色算法。設計了具有多對數運行時間的確定性[delta]1 + o(1)-著色算法。改進了(通常是次對數時間)的隨機算法。給出了大幅改進的下界。確定了在這些問題上比一般圖更快解決的廣泛圖族。

我們專著的目標是涵蓋這些發展的大部分,並作為在消息傳遞模型中分散式對稱破壞的理論基礎的論文。我們希望我們的專著能夠激發這個令人興奮的領域的進一步進展。

目錄:致謝 / 引言 / 圖論基礎 / 基本分散式圖著色算法 / 下界 / 森林分解算法和應用 / 有缺陷著色 / 有缺陷著色 / 邊著色和最大匹配 / 網絡分解 / 分散式隨機算法簡介 / 結論和開放問題 / 參考文獻 / 作者簡介