最大クリーク抽出問題は典型的なNP困難問題であり，理論的に非常に 重要である．さらに同問題は実用的に，符号理論，画像処理，バイオインフォマティクス，クラスタリング，周波数割当て，等々多くの問題解決に有効に活用できることが分かってきており，そのため近年非常に活発な研究が進められている．
本講演においては先ず，厳密な最大クリーク抽出のための効率的な分枝限定アルゴリズムについて，講演者らが開発してきた主要な幾つかの成果を紹介する．これらの結果は，国際的に広く引用されている．
なお，近年のアルゴリズムの中では，近似最大クリークを非常に高速に求めるKengo Katayamaらのアルゴリズムを有効に活用している．
続いて，上記問題の一般化に位置する，極大クリーク全列挙問題を考え，それを実行するための深さ優先探索アルゴリズムを紹介する．この種のアルゴリズムについての理論的計算量評価は長年にわたり未解決であったが，ここで初めて理論計算量を与え，しかもそれが理論的に最適な評価値となっていることを明らかにしている．さらに，当アルゴリズムは実働的にも高速であることを確認している．
上記の最大および極大クリーク抽出アルゴリズムについては，それらを実問題に対して成功裡に適用した幾つかの結果を紹介する． |
