情報処理学会ホームページ
FIT2013第12回情報科学技術フォーラム 開催日:2013年9月4日(水)~6日(金) 会場:鳥取大学鳥取キャンパス
抄録
A-003
最大クリーク問題に対する頂点次数を考慮しないk-opt局所探索法
渡邉好幸・片山謙吾・南原英生・西原典孝(岡山理大)
最大クリーク問題に対する強力な解法の多くは,クリークという部分グラフの特徴を考慮し,頂点の次数が大きい頂点を優先的に選択することでクリークを拡大する方法が一般的に利用される.また,これらの解法の多くはDIMACSベンチマークグラフに適用され,多くのグラフ例題に対して有効である場合が多い.しかしながら,その一方で,その効果が現れにくいグラフ例題も存在する.そこで本研究では,次数が大きい頂点を優先的に選択する一般的な方法とは異なり,頂点の次数を考慮せずにクリークの拡大を行う新たな局所探索法を提案する.