第25回セミナー・勉強会
日時: | 2022.05.30 Mon. 15:00-17:00
|
---|---|
会場: | オンライン |
話者: | 中畑 裕(奈良先端科学技術大学院大学,B01班) |
題目: | 決定グラフを用いた暗黙的部分グラフ列挙 |
概要: | グラフが与えられたとき,その部分グラフを列挙する問題は計算機科学における基本的な問題である.部分グラフの数は入力グラフのサイズに対して指数的に大きくなりうるため,全ての部分グラフを1個ずつ出力するのは実用的でない場合がある.そこで我々は暗黙的部分グラフ列挙に注目する.暗黙的部分グラフ列挙では,部分グラフを陽に列挙する代わりに部分グラフの集合を表す決定グラフ(DD)を構築する.本講演ではDDを用いた暗黙的部分グラフ列挙に関する最近の研究を紹介する.
|
2022.05.17 更新