14:30 〜 14:50
[2I4-OS-9a-03] 最大独立集合問題のSAT技術を用いた解法に関する研究
キーワード：最大独立集合問題、充足可能性判定問題、制約充足問題、SATソルバー
独立集合とは，与えられた無向グラフの隣接する頂点を含まない部分頂点集合である．最大独立集合問題は，基数が最大の独立集合を求める問題であり，スケジューリング問題やDNAシークエンシングなどを解くのに用いられる．近年，命題論理式の充足可能性判定 (SAT) 問題を解くプログラムであるSATソルバーの性能が飛躍的に向上している．本論文では，SATソルバーを用いた最大独立集合問題の解法を提案する．具体的には，基本制約モデルとクリーク分割を利用した改良制約モデルの2つの制約モデルを提案する．また，探索の過程で得られた学習節を再利用することで高速化を図るインクリメンタルSAT解法を用いた最大独立集合問題の解法アルゴリズムについても提案を行う．提案手法の評価として，既存の最大独立集合問題の専用手法との評価を行い，提案手法の有効性を確認した．
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。