05月12日(Mon) 15:20〜17:00 D会場(48人-ひめぎんホール 第3会議室)
| 演題番号 | 1D4-OS-11a-3 |
|---|---|
| 題目 | Size complexity of BDD construction of Pseudo-Boolean constraints in binary/mixed-radix base form |
| 著者 | 永塚 尚紀(名古屋大学 大学院情報科学研究科 計算機数理科学専攻) 酒井 正彦(名古屋大学 大学院情報科学研究科) Zankl Harald(インスブルック大学) 草刈 圭一朗(岐阜大学 工学部) |
| 時間 | 05月12日(Mon) 16:15〜16:30 |
| 概要 | 各々の擬ブール制約をBDDを経由してCNFに変換し、それらをまとめて SATソルバで解く手法において，Avioらは制約の係数を2進展開し、昇順でBDD を生成することでそのサイズが多項式で抑えられることを示した．本論文では、 2進展開された制約から降順でBDDを生成してもそのサイズが多項式で抑えられること示す．また、展開法の拡張を提案し、MiniSat+に実装・実験した結果を述べる． |
| 論文 | PDFファイル |