@techreport{oai:ipsj.ixsq.nii.ac.jp:00212246,
 author = {武田, 浩和 and 斎藤, 寿樹},
 issue = {7},
 month = {Aug},
 note = {区間グラフは区間の集合を表現に持つグラフである．真区間グラフは区間グラフの部分クラスで，どの区間も他のどの区間とも包含関係にない区間の集合を表現に持つグラフである．グラフ同型性を考慮した真区間グラフの列挙アルゴリズムとして逆探索法を用いたものが知られている．このアルゴリズムはグラフ 1 つあたりの出力に O(1) 時間で，理論的に効率的であるものの，グラフの頂点数が大きくなると真区間グラフの数は膨大となり，すべてを出力することはできない．一方で，ゼロサプレス型二分決定グラフ (ZDD) は組み合わせ集合をコンパクトに表現できるデータ構造で，最適化問題や列挙問題を効率的に処理できるとして近年，注目を集めている．本研究では ZDD を用いた真区間グラフを高速に列挙するアルゴリズムを提案する．提案アルゴリズムすべての真区間グラフを表現する ZDD を頂点数 n の多項式時間・領域で構築する．これまでの逆探索法では実験的に頂点数 n=18 までしか列挙できなかったのに対し，提案アルゴリズムでは n=700 の真区間グラフを容易に計算可能となる．また本アルゴリズムは，頂点数だけでなく，最大クリークサイズや辺の本数などの制約を加えた真区間グラフもわずかな拡張によって列挙することができる．本稿ではこれらのアルゴリズムを解析するとともに，計算機実験によりその効率性を示す．},
 title = {真区間グラフの高速な列挙アルゴリズムとその応用},
 year = {2021}
}