最大独立集合問題のSAT技術を用いた解法に関する研究

DOI

書誌事項

タイトル別名
  • A SAT-based Method for Solving the Maximum Independent Set Problem

抄録

<p>独立集合とは，与えられた無向グラフの隣接する頂点を含まない部分頂点集合である．最大独立集合問題は，基数が最大の独立集合を求める問題であり，スケジューリング問題やDNAシークエンシングなどを解くのに用いられる．近年，命題論理式の充足可能性判定 (SAT) 問題を解くプログラムであるSATソルバーの性能が飛躍的に向上している．本論文では，SATソルバーを用いた最大独立集合問題の解法を提案する．具体的には，基本制約モデルとクリーク分割を利用した改良制約モデルの2つの制約モデルを提案する．また，探索の過程で得られた学習節を再利用することで高速化を図るインクリメンタルSAT解法を用いた最大独立集合問題の解法アルゴリズムについても提案を行う．提案手法の評価として，既存の最大独立集合問題の専用手法との評価を行い，提案手法の有効性を確認した．</p>

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390578283197875328
  • DOI
    10.11517/pjsai.jsai2023.0_2i4os9a03
  • ISSN
    27587347
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ