圧縮索引を用いたグラフ上のウォーク列挙及び数え上げ

点击翻译按钮获取中文摘要

"汎用的なウォークセット索引の構築手法の設計"を行うために，グラフの任意の2点間のk-ステップウォークの列挙・索引化を可能とするデータ構造をSeqBDDを用いて構築するアルゴリズムの開発及び計算機実験を行った．これらの結果について，[1]にて発表を行った．さらに，構築したデータ構造を用いて，"訪問回数制限ウォークの列挙，数え上げ問題"に取り組むために，グラフ上の頂点を訪問する回数(頂点被覆回数)に下限と上限の制限を与えたウォークを列挙・索引化する手法を考案・実装した．これらの結果について，[2]にて発表を行った．さらに，サブセッティング法と呼ばれるZDDを高速に構築するための手法を本手法で用いるSeqBDDにも適用する方法を考案し，これを用いて訪問回数制限ウォークをより高速に列挙・索引化する手法について，[3]にて発表を行った．これらの研究による手法は，愚直に1つずつ列挙することが困難な膨大な数のウォークを索引として非明示的にまとめて列挙することができている．本年度の研究では，ウォーク列挙の基盤となる"2点間のk-ステップウォーク"を列挙・索引化することに成功し，構築した索引を特定のウォークを見つけることに応用するための一例として，"訪問回数制限ウォーク"の列挙・索引化を行った．