FIT2016 第15回情報科学技術フォーラム 開催日:2016年9月7日(水)~9日(金) 会場:富山大学キャンパス
抄録
A-023
可変j-核および可変k-Plex 性を用いた孤立性擬似クリークの全列挙について
Hongjie Zhai・原口 誠(北大)
擬似クリークの全列挙に関しては長年にわたり精力的な研究がなされてきたが,頂点集合としてのサイズが比較的大な場合はグラフクラスタリングで十分であろう.
問題はサイズが中規模以下の擬似クリークを対象にしたときであり,その総数は爆発的に増大し,現実的な列挙は困難になる.
こうした事情に鑑み,本研究においては,ターゲットとなる頂点集合のサイズレンジを設定し,それに応じて孤立性を持つ密結合の頂点集合を漏れなく列挙できる手法を,接続数下限制約を定める j(x),および非接続数上限制約を設定する k(x)という2つの関数に基づいて実現する方式について論じる.