08 2018/09 10
26272829303101
0203 04 05 060708
0910 1112131415
16171819202122
2324 25 26 272829
30010203040506
Click セミナー

過去のセミナー

開催日2018年5月29日(火曜日)
開催時間16時30分-17時30分
発表者鈴木 浩史 
発表者の紹介北海道大学
タイトルフロンティア法と集合族演算の合わせ技 
発表の概要
Knuthが示したパス列挙アルゴリズムにはじまり,ZDDを用いたグラフ列挙技法であるフロンティア法が発展してきた.一方で,ZDD本来の特色である集合族演算も依然として重要である.本発表では,フロンティア法と集合族演算をふんだんに活用した,グラフ最適化問題に対するZDD的アプローチ(解の列挙)について議論したい.事例としてネットワーク設計問題を取り上げ,基本的なアプローチを解説する.
開催場所VBL 301B
接続サイト神田ラボ,京大ラボ
 
開催日2018年5月29日(火曜日)
開催時間17時30分-18時30分
発表者山崎 一明 
発表者の紹介JAIST
タイトルEnumeration of Nonisomorphic Graphs in Glaph Classes 
発表の概要
同型性判定が多項式時間で行えるグラフクラスについて,そのグラフクラスに属する全グラフを一つあたり多項式時間遅延で列挙するアルゴリズムを構成するためのフレームワークを定式化した.また,同型なグラフは本質的に同一なものであると考え,同型なグラフはちょうど1度だけ出力する.このフレームワークを用いることで,望むグラフクラスについて容易に列挙アルゴリズムを開発することができる.本研究ではグラフ列挙のためのフレームワークとして Reverse Search用いる.また,提案したフレームワークを Interval Graph と Permutation Graph について適用し,実際に列挙アルゴリズムを構成することで,フレームワークの有用性を確かめた.今回の発表では,フレームワークの概要及び,Interval Graph に対する適用について話す.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ