06 2020/07 08
28293001020304
05060708091011
12131415161718
19202122232425
26272829303101
Click セミナー

過去のセミナー

開催日2019年5月21日(火曜日)
開催時間15時00分-16時00分
発表者中畑 裕 
発表者の紹介京都大学
タイトルトポロジカルマイナーで特徴づけられる部分グラフの列挙索引化 
発表の概要
"グラフが与えられたとき,その部分グラフであって条件を満たすものを効率よく列挙する問題は,計算機科学における基本的な問題である.
一般的な列挙アルゴリズムは,解(条件を満たす部分グラフ)を1つずつ陽に出力する.
一方で,解を陽に出力せず,解集合を圧縮表現するZDDを直接構築するアルゴリズムが研究されており,その枠組みはフロンティア法と呼ばれている.
いったんZDDを構築できると,ZDDを解の索引として利用することで,ネットワーク信頼性など,応用上重要な様々な計算が可能である.
そのため,フロンティア法で扱える部分グラフの種類を拡大することが,ZDD技法の応用範囲を拡大する上で重要である.

本研究では,グラフのトポロジカルマイナーによる特徴づけを用いて,様々な部分グラフ集合を表すZDDを構築するための統一的なアルゴリズムの枠組みを提案する.
提案手法は,平面的グラフ,外平面的グラフ,直並列グラフ,カクタスグラフなど,従来の手法では扱えなかった様々な種類の部分グラフを,統一的な枠組みで扱える.
計算機実験において提案手法を平面的な部分グラフの列挙に適用した結果,
提案手法が愚直なバックトラック法より高速に動作することを示す.

本研究は,川原純氏,堀山貴史氏,湊真一氏との共同研究である."
開催場所VBL301B
接続サイト神田ラボ,京大ラボ