あらまし

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

伊藤 大雄 

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-孤立クリークを全列挙するアルゴリズムについて述べる.これらの計算時間も,前述のものと同様の意味で計算時間の限界値を達成している.

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355