抄録

◎伊藤　華・井上祐馬・湊　真一（北大）

本稿では，与えられたグラフから制約を満たす部分グラフを列挙する問題を取り扱う。このような問題は多方面への応用が可能であり，解法の模索は重要と言える．近年この問題に対し，ZDDをトップダウンで構築することで高速に解を与えるフロンティア法というアルゴリズムに注目が集まっている．このアルゴリズムはグラフの変数処理順序で性能が大きく左右されることが知られている．本稿では，構築されるZDDのサイズを抑えて処理を高速化する為，フロンティアと呼ばれる処理済頂点と未処理頂点の境界に含まれる頂点数を抑える変数順序を与える発見的手法を提案する．また，本稿の手法と既存の順序づけ法での実験結果を比較し評価を行う．