A-009
グラフウォークを列挙する系列二分決定グラフの高速な生成法に関する実験と評価

◎石丸　亮・青木洋士・湊　真一（北大）

本稿では、グラフにおけるウォークの列挙索引化について述べる。頂点の重複を許さないウォークは、使用する辺の組合せを扱うZDDにより効率よく実現できることが知られているが、それ以外のウォークは辺を通る順序や回数を記憶する必要があるためZDDで列挙索引化を行うことは困難である。そこで本稿では、ZDDではなく系列集合を表現する系列二分決定グラフ（SeqBDD）を用いて、ウォークを列挙するSeqBDDを構築する方法を提案し、実験によりその有効性を評価する。