[4K1-OS-16a] [Organized Session] OS-16

[4K1-OS-16a-03] Enumerating Acyclic Contractions of a Directed Acyclic Graph Using Frontier-Based Search

〇Yu Nakahata¹, Hirofumi Suzuki², Masakazu Ishihata², Takashi Horiyama³ (1. Nara Institute of Science and Technology, 2. Hokkaido University, 3. Saitama University)

Keywords:Graph algorithm, Decision diagram, Frontier-based search, Enumeration problem

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