11 2019/12 01
01 02 03 04 050607
08091011121314
15161718192021
22232425262728
29303101020304
Click セミナー

過去のセミナー

開催日2019年12月3日(火曜日)
開催時間16時30分-17時30分
発表者和佐 州洋 
発表者の紹介国立情報学研究所
タイトルThe Perfect Matching Reconfiguration Problem 
発表の概要
本発表では,完全マッチング遷移問題について発表する.この問題は,グラフにおける完全マッチングが二つ与えられた時,これらを次に定義するフリップ操作を繰り返し適用することで一方の完全マッチングからもう一方に変形できるかを問う問題である.ここでフリップ操作とは,長さ4のマッチングに使われている辺と使われていない辺が交互に現れる閉路を一つ選び,マッチングに使うかどうかを逆転させるものである.この問題に対して,我々は,スプリットグラフ,あるいは,バンド幅が定数で最大次数が5の二部グラフ,に対してもPSPACE完全であることを述べる.さらに,強orderableなグラフ,外平面グラフ,あるいは,コグラフが入力である時に,多項式時間アルゴリズムが存在することを述べる.また,これらのグラフクラスに対して,もし入力が真となるインスタンスであった時に,たかだか線形回のフリップ操作を適用することで目的の完全マッチングが得られることを示し,実際にそのような列を多項式時間で構成できることも述べる.
開催場所VBL301B
接続サイト神田ラボ、京大ラボ