/ プログラム/ 発表一覧/ 著者一覧企業展示一覧/ jsai2015ホーム /

2H5-OS-03b-4 SAT問題におけるCommunity rankの提案

*セッションの無断動画配信はご遠慮下さい。

Tweet #jsai2015 このエントリーをはてなブックマークに追加

05月31日(Sun) 17:20〜19:00 H会場(5F北-小講義室 (583))
2H5-OS-03b オーガナイズドセッション「OS-3 SAT技術の理論,実装,応用 (2)」

演題番号2H5-OS-03b-4
題目SAT問題におけるCommunity rankの提案
著者戸ヶ崎 仁宣(東京大学大学院情報理工学研究科創造情報学専攻)
手塚 宏史(東京大学大学院情報理工学系研究科創造情報学専攻)
稲葉 真理(東京大学大学院情報理工学系研究科創造情報学専攻)
時間05月31日(Sun) 18:20〜18:40
概要SAT問題を、隠された問題の構造を利用して効率的に解くためにCNFから関連の深い変数のCommunityを抽出する。そして優先的に探索するCommunityを選択するためにCommunity Rankを提案し、改良版MiniSat2.20にCommunity Rankを実装しSAT competition 2014のApplication問題について実験を行った。
論文PDFファイル