BDD/ZDDを用いたグラフ列挙索引化技法

摘要

本稿では,与えられたグラフ構造のなかから,ある制約条件を満たすような部分グラフ構造をすべて列挙し,それらをBDD/ZDDを用いて圧縮表現して索引化する技法について述べる.まず,BDD/ZDDとその演算処理系について簡単に説明し,次に,ZDDを用いた高速なパス列挙索引化アルゴリズムSimpathの概要を解説する.このアルゴリズムはKnuthが近年提案したものであるが,制約条件によって多くのバリエーションが存在することから,われわれはそれらを総称して「フロンティア法」と呼んでいる.本稿ではフロンティア法がなぜ高速であるか,そして従来のBDD/ZDDを用いた制約充足問題の解法との違いについて述べる.