第07回セミナー・勉強会
日時: | 2021.02.19 Fri. 15:00-17:00
|
---|---|
会場: | オンライン |
話者: | 川原 純(京都大学,B01班) |
題目: | ZDDを用いた部分グラフ列挙 |
概要: | ゼロサプレス型二分決定グラフ(ZDD)は集合族を圧縮して表現するデータ構造である.与えられたグラフに対して,パスや全域木などの部分グラフを列挙し,ZDDとして表現するアルゴリズムが知られている.さらに,部分弦グラフや部分区間グラフ,部分平面グラフなどの集合を表すZDDを構築するアルゴリズムが提案されている.構築したZDDはホットスポット検出や選挙区割問題,ペンシルパズルソルバーなどのグラフ最適化問題に応用できる.本発表では,ZDDの基本的な性質を解説した後,ZDDを用いた部分グラフ列挙に関する最近の研究を紹介する.
|
2021.02.12 更新