クリーク列挙──アルゴリズムと下限──

伊藤　大雄

あらまし

クリーク列挙──アルゴリズムと下限──

伊藤　大雄

Vol.95 No.6pp.484-489

発行日:2012/06/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　広がる列挙の技術──列挙による問題解決アプローチ──

専門分野:

キーワード:
極大クリーク, 列挙, 孤立クリーク, ピボット, 下界値,

本文:PDF(518.6KB)>>

あらまし:
グラフにおいて，任意の頂点対間に辺のある部分グラフのことをクリークという．クリークを発見することは，Webグラフにおけるコミュニティの発見などの応用面から，近年注目を浴びている．本稿では，極大なクリークを総列挙するアルゴリズムについて説明する．まず極大クリークは最大で指数（Θ(3^n/3)）個存在する場合があることを示し，次に富田らの提案したO(3^n/3)時間で極大クリークを全列挙するアルゴリズムを説明する．これは上記のグラフの存在からオーダの意味で計算時間の限界値を達成している．次に，周りとのつながりが疎である，孤立クリークの概念を説明し，孤立性を表すパラメータc が定数の場合は線形時間で，c=O(log n)の場合は多項式時間でc-孤立クリークを全列挙するアルゴリズムについて述べる．これらの計算時間も，前述のものと同様の意味で計算時間の限界値を達成している．

あらまし

ログイン

メニュー