06月12日(Tue) 10:00〜12:20 E会場(-山口県教育会館／第四研修室(72))
| 演題番号 | 1E1-R-1-3 |
|---|---|
| 題目 | グラフ彩色インスタンスの組織的生成のための極小非可解構造の導出 |
| 著者 | 水野 一徳(拓殖大学工学部情報工学科) 西原 清一(筑波大学大学院コンピュータサイエンス専攻) 佐々木 整(拓殖大学工学部情報工学科) |
| 時間 | 06月12日(Tue) 10:40〜11:00 |
| 概要 | 本研究では，解くのに非常に手間のかかるグラフ彩色インスタンスを組織的に生成する方法を開発している．本方法は，極小非可解構造（MUS）を互いに繰り返し埋め込むことにより，任意に大きく難しいインスタンスを安定的に生成するものである．本報告では，本方法に必須のMUSを，遺伝的アルゴリズムを用いて導出することを試みる．また．生成したインスタンスを解く計算量が問題サイズの指数オーダになることを実験的に示す． |
| 論文 | PDFファイル |