抄録

◎ホリルロハマン ムハマド（北大）・湊　真一（北大/JST）

本研究では、同じ頂点を高々2回まで通ることを許す経路の数え上げを考える。バックトラック法を使うと解の個数に比例する時間がかかるので実行時間がかかりすぎる。筆者らは以前に、経路を無向グラフとして扱い、各辺の通過回数のパターンを4分木を使って高速に数え上げるアルゴリズムを提案した。しかし、その方法では同じパターンを持つ経路が複数存在する場合があり、経路数の下界を求めたことになる。本発表では無向グラフの代わりに有向グラフを用いて、経路の通過回数パターンをより正確に数えるアルゴリズムを提案する。本手法でも経路数の下界を計算していることに変わりはないが、前回の実験結果より真の経路数に近くなることが分かった。