2.クリーク列挙 : アルゴリズムと下限(<小特集>広がる列挙の技術-列挙による問題解決アプローチ-)
スポンサーリンク
概要
- 論文の詳細を見る
グラフにおいて,任意の頂点対間に辺のある部分グラフのことをクリークという.クリークを発見することは,Webグラフにおけるコミュニティの発見などの応用面から,近年注目を浴びている.本稿では,極大なクリークを総列挙するアルゴリズムについて説明する.まず極大クリークは最大で指数(Θ(3^<n/3>))個存在する場合があることを示し,次に富田らの提案したΟ(3^<n/3>)時間で極大クリークを全列挙するアルゴリズムを説明する.これは上記のグラフの存在からオーダの意味で計算時間の限界値を達成している.次に,周りとのつながりが疎である,孤立クリークの概念を説明し,孤立性を表すパラメータcが定数の場合は線形時間で,c=Ο(log n)の場合は多項式時間でc-孤立クリークを全列挙するアルゴリズムについて述べる.これらの計算時間も,前述のものと同様の意味で計算時間の限界値を達成している.
- 2012-06-01