| 14:00--15:50 | 『Holt-Klee 条件から見た有向マトロイドの実現不可能性』 | 東京大学 森山園子 氏 |
|---|
|
有向マトロイドとは，
Rnの線形部分空間を組合せ的に抽象化した
組合せ幾何学の基本構造である．
与えられた有向マトロイドがRnの線形部分空間から得られるとき，
実現可能であるというが，
この判定問題はNP-困難であることが知られている．
本研究では，実現可能有向マトロイドを含む２つのクラス，
HK有向マトロイドおよびHK*有向マトロイドを定義し，
実現不可能な有向マトロイドの新たな構成法を提案する．
HKおよびHK*は多面体的グラフのLP-向き付けが満たすHolt-Klee条件を
基にした性質である．
本研究は，福田公明(ETHZ,EPFL)，岡本吉央(ETHZ)との共同研究である．
|
| |
| 16:10--18:00 | 『シミュレーション用擬似乱数の配置問題とグラフの彩色問題』 | お茶の水女子大学 萩田真理子 氏 |
|---|
並列計算機でシミュレーションをするときに、各計算機で擬似乱数を発生させて用いることがあります。（例： 核分裂の様子を調べるとき、空間を小さな区域に分割して、それぞれの領域での確率現象を、各計算機で生成した擬似乱数を用いて計算させる。）しかし、近くの現象を扱う計算機が全く同じ擬似乱数列を生成していたら、それによる偏りがおきてしまいます。相関が大きい場所では、なるべく違う関数で生成された擬似乱数を用いた方が正しい結果を得られます。何種類かの関数しかないときに、どのように割り振れば良いでしょうか？ この問題はグラフの彩色問題として書き表すことができます。
本講演では、４色定理やラムゼー理論など、古くから行われてきたグラフの彩色に関わるグラフ理論の解説と、シミュレーションのためのグラフ彩色の研究の紹介をします。
|
|