活動情報

イベント詳細

第07回セミナー・勉強会

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