平成 22 年度第 2 回 ＯＲ横断若手の会(KSMAP)

日時：5月29日（土） 15:30〜18:00
場所：京都大学工学部８号館３階共同５講義室

テーマと講師：

(1) 谷川眞一 （京都大学）
「３次元構造物の組合せ剛性とその応用」

３次元構造物(伸び縮みのない棒材がピンで接合された構造物)の
一般剛性を多項式時間で判定する問題は，剛性理論において
最も基本的であるにも関わらずこれまで未解決である．
本講演では，このような問題の定義や背景を解説するとともに，
現在解くことができる特殊ケース，および，
剛性理論の応用例について幾つか紹介がなされた．


(2) 高澤兼二郎 （京都大学）
「制約付き 2-マッチング問題についての最近の研究動向と未解決問題」

無向グラフ G=(V,E) において，枝数が k 以下の閉路を含まない
2-マッチングを C_k-free 2-マッチングと呼ぶ．C_k-free
2-マッチング問題は， k が 2 以下ならば古典的な 2-マッチング
問題である一方で，k が |V|/2 以上ならばハミルトン閉路問題を
含む問題となる．本講演では，C_k-free 2-マッチング 問題について，
未解決問題および最近の研究の進展について紹介がなされた．