日時：1月23日（金） 15:00〜17:30
場所：京都大学 工学部８号館共同５号室
http://www.kuamp.kyoto-u.ac.jp/map/index-map.html
http://www.i.kyoto-u.ac.jp/top/address.html
講演題目と講演者：
・ 上嶋 章宏
（京都大学大学院 情報学研究科 通信情報システム専攻 博士後期課程）
「H-彩色可能なグラフのクラスの階層構造と平面グラフのH-彩色問題の計算複雑さ」講演要旨
・ 柳井 秀三
（神戸商科大学大学院 経営学研究科 経営情報科学専攻 博士後期課程）
「ある１機械スケジューリング問題に対する優越テストについて」講演要旨
H-彩色可能なグラフのクラスの階層構造と平面グラフのH-彩色問題の計算複雑さ
上嶋 章宏（京都大学大学院 情報学研究科 通信情報システム専攻 博士後期課程）
H-彩色問題は，代表的な離散最適化問題の一つであるグラフの点彩色問題に， 単純で自然な一般化を施した問題であり，入力されたグラフGからHへの準同形 写像が存在するか否かを問う問題と表現できる．その計算複雑さは，Gが一般 のグラフの場合，Hが2部グラフならば多項式時間可解，Hが非2部グラフならば NP-完全であることは示されているが，Gを平面グラフに限定した場合，Hが非2 部グラフのとき未解決である． 本発表ではこの未解決問題に注目し，従来のn-彩色が有する“n-彩色可能なグ ラフの集合はn+1-彩色可能なグラフの集合の真部分集合である”という自明な 階層構造を内包し，無限に細分化する新たな階層構造を提案し，この階層構造 に従い，平面グラフのH-彩色問題の計算複雑さがNP-完全から多項式時間可解 に変化する境界を探る．
ある１機械スケジューリング問題に対する優越テストについて
柳井 秀三（神戸商科大学大学院 経営学研究科 経営情報科学専攻 博士後期課程）
優越テスト(dominance test)は分枝限定法における限定操作の一つであり， 良い下界値が得られないスケジューリング問題では重要な技法とされている． リリース時刻付き総滞留時間最小化１機械スケジューリング問題に対して， さまざまな種類の優越テストを組み合わせることにより，ジョブ数100の問題が 現実的な計算時間で解けたと報告されている．しかし，そこで提案されている 各優越テストは，単体では正しいものの，それらを単純に組み合わせると最適 解を得る前にすべての子問題が限定され，最適解を出力せずに分枝限定法が終了 してしまう可能性がある．本発表ではまずその点を指摘し，続いて分枝限定法が 正しく動くための修正方法を提案する．さらに新しい優越テストを提案する． 最後に数値実験結果を報告する．