並列アルゴリズムと分散アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
「グラフ彩色」の記事における「並列アルゴリズムと分散アルゴリズム」の解説
グラフ彩色の分散アルゴリズムは、グラフの「対称性の破れ」の問題と密接に関連する。対称グラフでは、決定的分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、n 個の各頂点に {1, 2, ..., n} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは n 色を例えば Δ + 1 色にまで減らしていくことである。 貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ(n) 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。 単純で興味深い例として n-閉路グラフがある。Richard Cole と Uzi Vishkinによれば、1回の同期通信ステップで色数を n から O(log n) に減らす分散アルゴリズムが存在する。これを繰り返すとn-閉路グラフの3-彩色を O(log* n) の通信ステップで得ることができる（各頂点には一意の識別子が付与されていることが前提）。 反復対数関数 log* は成長が非常にゆっくりとしていて、ほぼ定数とみなせる。そこで Cole と Vishkin の成果から、n-閉路の3-彩色を求める定数時間の分散アルゴリズムはあるのかという問題が提起される。Linial (1992) によれば、そのようなアルゴリズムは存在しない。決定的分散アルゴリズムはn-閉路をn-彩色から3-彩色に減らすのに Ω(log* n)の通信ステップを必要とする。 ColeとVishkinの技法は任意の次数の制限されたグラフに適用可能である。その場合の計算時間は poly(Δ) + O(log* n) となる。(Δ + 1)-彩色の既知の最高速アルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算時間は O(Δ) + log*(n)/2 であり、Linialの下限によれば 1/2 という係数はこれ以上改善できないので n に対して最適なアルゴリズムということになる。 辺彩色の分散アルゴリズムも研究されてきた。Panconesi & Rizzi (2001) では、(2Δ − 1)-辺彩色を O(Δ + log* n) の時間で可能なアルゴリズムが示されている。Linial (1992) による分散頂点彩色の下限は、辺彩色問題についても同様に成り立つ。
※この「並列アルゴリズムと分散アルゴリズム」の解説は、「グラフ彩色」の解説の一部です。
「並列アルゴリズムと分散アルゴリズム」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
- 並列アルゴリズムと分散アルゴリズムのページへのリンク
