2006.07.26

Research

最小全域木の文献(調査候補1/5)

Computing a Diameter-Constrained Minimum Spanning Tree in Parallel

『直径制約あり最小全域木の並列計算』とでも訳せばいいのか?
Diameter-Constrainedは「k個以上のエッジを持つパスが存在してはいけない」という制約を意味するのだと思うのだが...よく分からん。とりあえずアブストだけ訳してみた。

Abstract

最小の直径を持つ最小MST(DCMST)は様々なシチュエーションで要求される。実際に、分散した相互排他的なアルゴリズムでは、クリティカルセクション毎にプロセッサ間で発生するメッセージの数を最小化する為にDCMSTを用いる。DCMST問題は以下の用に規定される。

『nノードからなる重み付き無向グラフGが存在し、任意の自然数kが与えられる時、重みの合計が最小となる全域木を見つける。ただしk個以上のエッジを持つパスが存在してはいけない。』

この問題はkが4〜n-2の範囲においてNP完全問題であることが知られている。したがってこれらの問題ではヒューリスティクスにより近似解を求めることが関心事となる。

本論ではDCMST問題に適用する2つのヒューリスティクスについて述べる。一つはone-time-tree-constructionアルゴリズムというアルゴリズムで、これは改良欲張り法によりDCMSTを生成する手法である。この手法ではヒューリスティックスを、毎ステップごとにツリーに加えるエッジを選択するフェーズで利用する。このアルゴリズムは高速かつ並列化が容易である。またこの手法はnとは独立に、kが小さい場合に特に適した手法である。2つ目の手法は制約無しMSTからスタートし、毎ステップ毎に、k個のエッジを持つパスが無くなるまで、長いエッジを一つ一つ交換してゆくことで最終的な解を得る。このヒューリスティックスはkが大きい場合に有効である。

本論ではこれらのヒューリスティクス法について、その収束性と相対的メリット、MasPar MP-1(SIMD型超並列マシン:8192CPUs)上での並列化の実装について検討した。多様な実験の結果、2つのヒューリスティクスが様々な問題に対して優れた解探索性能を示した。