[4K1-OS-16a] AI における離散構造処理と制約充足(1)

[4K1-OS-16a-03] フロンティア法によるDAGの非巡回縮約の列挙

〇中畑 裕¹、鈴木 浩史²、石畠 正和²、堀山 貴史³ (1. 奈良先端科学技術大学院大学、2. 北海道大学、3. 埼玉大学)

キーワード：グラフアルゴリズム、決定グラフ、フロンティア法、列挙問題

有向非巡回グラフ（DAG）は計算機科学における基本的な構造である．
応用において，DAGをより小さなDAGに縮約する問題は，命令セット拡張問題等のために重要である．
本研究では，DAGが与えられたとき，いくつかの辺を選んで縮約した結果がDAGとなるような辺の選び方をすべて列挙するアルゴリズムを提案する．
提案手法はフロンティア法に基づき，所望の辺部分集合の族を表現するデータ構造ZDDを構築するアルゴリズムである．