06月05日(Wed) 18:00〜20:20 E会場(-国際会議場204号室)
| 演題番号 | 2E5-OS-09b-5 |
|---|---|
| 題目 | SCSatを用いたラムゼー数の下界更新について |
| 著者 | 藤田 博(九州大学大学院システム情報科学研究院情報学部門) |
| 時間 | 06月05日(Wed) 19:20〜19:40 |
| 概要 | SATソルバーを用いてラムゼー数に関する問題を解く。 そのCNF記述は数千変数、数千万節に及び、莫大な探索空間内 で充足解の密度は極めて小さく、求解は著しく困難である。 そこで、問題に何らかの対称性を仮定し、探索領域を絞り込む。 想定した対称解が得られない場合、対称性制約を適宜緩める。 この手法により、ラムゼー数R(4,8)の既知の最良下界55を 56に更新することに成功した。 |
| 論文 | PDFファイル |