16:10 〜 16:30
[2I5-OS-9b-03] CompDP: 複数の連結性制約の下の部分グラフ数え上げを同時に行う動的計画法
キーワード：二分決定グラフ、数え上げ
元のグラフに対し，特定の制約を満たす部分グラフの数を数える問題が部分グラフ数え上げ問題である．種々のグラフ制約の中でも，ある頂点と別の頂点が連結である，などのグラフの連結性に関する制約は特に重要で，その下での数え上げは，例えばある頂点を通る経路が何本存在するかなど，その頂点が通信網や配電網の中でどれほど重要かを表す指標の計算に応用できる．一方で，各頂点に対してそのような指標を計算するためには一般に同様の数え上げ問題を複数回にわたり解くことになるが，従来は各々別々にBDD/ZDD等の決定グラフを構築し計算を行う必要があった．本研究では，こうした複数の数え上げ問題を解く際に現れる似通った連結性制約に着目し，それぞれの制約下の部分グラフ数え上げを同時並行に解くアルゴリズムを提案する．実験により，いくつかの問題設定において従来の個別に決定グラフを構築する方法と比べて提案法が10〜20倍高速に全ての頂点に対する数え上げを行えることを確かめた．
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。