クリーク列挙──アルゴリズムと下限──
Vol.95 No.6pp.484-489
発行日:2012/06/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 広がる列挙の技術──列挙による問題解決アプローチ──
専門分野:
キーワード:
極大クリーク, 列挙, 孤立クリーク, ピボット, 下界値,
本文:PDF(518.6KB)>>
あらまし:
グラフにおいて,任意の頂点対間に辺のある部分グラフのことをクリークという.クリークを発見することは,Webグラフにおけるコミュニティの発見などの応用面から,近年注目を浴びている.本稿では,極大なクリークを総列挙するアルゴリズムについて説明する.まず極大クリークは最大で指数(Θ(3n/3))個存在する場合があることを示し,次に富田らの提案したO(3n/3)時間で極大クリークを全列挙するアルゴリズムを説明する.これは上記のグラフの存在からオーダの意味で計算時間の限界値を達成している.次に,周りとのつながりが疎である,孤立クリークの概念を説明し,孤立性を表すパラメータc が定数の場合は線形時間で,c=O(log n)の場合は多項式時間でc-孤立クリークを全列挙するアルゴリズムについて述べる.これらの計算時間も,前述のものと同様の意味で計算時間の限界値を達成している.