07 2018/08 09
29303101020304
05060708091011
12131415161718
19202122232425
26272829303101
Click セミナー

過去のセミナー

開催日2018年5月30日(水曜日)
開催時間16時30分-17時30分
発表者栗田 和宏 
発表者の紹介北海道大学
タイトル疎なグラフに対する支配集合の効率良い列挙 
発表の概要
支配集合とは,グラフに含まれる任意の頂点が,支配集合に含まれる,もしくは支配集合中のある頂点と隣接する頂点集合である.極小な支配集合の列挙は,列挙問題の中心的な問題である極小なハイパーグラフ横断(ヒッティングセットとも呼ぶ)と等価な問題であり,いくつかのグラフクラスで出力多項式時間列挙が可能であることが示されている.しかし,極小支配集合列挙は,一般のグラフに対して,出力多項式時間で列挙できるかは未解決問題である.そこで本研究では,極小性を除いた問題である,支配集合列挙問題に取り組み,疎なグラフに対する2つの効率良いアルゴリズムを提案する.ここで,グラフの疎性として,縮退数と内周を用いる.1つ目のアルゴリズムは,縮退数kのグラフに対して,解1つあたりO(k)時間で解を列挙するアルゴリズムを与える.これは縮退数が定数のグラフに対して,最適に解を列挙する.2つ目に,内周が9以上のグラフに対して,解1つあたり定数時間で列挙するアルゴリズムを与える.本研究は国立情報学研究所の宇野毅明教授と,和佐州洋特任助教,北海道大学の有村博紀教授との共同研究である.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ
開催時間17時30分-18時30分
発表者中畑  裕 
発表者の紹介奈良先端科学技術大学院大学
タイトルフロンティア法によるDAGのDAGへの縮約の列挙 
発表の概要
本研究では,DAGが与えられたとき,その辺部分集合であってそれらを縮約した結果がDAGに
なるようなものを列挙するアルゴリズムを提案する.
この問題はハードウェア設計における命令セット拡張問題に応用がある.
提案法はフロンティア法に基づき,所望の辺部分集合の族を表すZDDを効率よく構築する.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ