抄録

○Hongjie Zhai・原口　誠・大久保好章（北大）・富田悦次（電通大）

クリーク緩和モデルの一つである k-Plex は，単調性を持つことか
ら，クリーク同様の全列挙手法を設計できる利点がある．一方，比
較的に大きな k に対しては，実際問題として中規模な疑似クリーク
に成長するまでの組み合わせに対しては有効でないという問題点が
あった．本発表では，この問題を解決するために，密な部分を含む
連結グラフを求める際の制約として有効な j-核性制約を新たに組み
込み，小規模な疑似クリークから比較的に中規模なクリーク列挙ま
で有効な手法を提案し，その有効性を検証する．