指数分布に従う枝長さと小さな木幅を持つ無向グラフ上での二点間の確率的な最短路長さの計算方法

スポンサーリンク

概要

論文の詳細を見る
本稿では,二点間の確率的な最短路問題に対する解法を提案する.確率的な最短路問題においては,与えられた無向グラフGの各枝の長さが確率変数として与えられ,二点間の最短路長さもまた確率変数となる.本研究の目的はグラフGの最短路長さの分布関数を求めることである.まず本稿では,確定的な枝長さが与えられた場合の最短路問題が多項式時間で解けることとは異なり,確率的な最短路問題について,離散的な二値を取り得る枝長さを考えるとパスグラフにおいても#P-完全である事をまず示す.次に,指数分布に従う枝長さを考えた場合にはこの確率的最短路問題をある程度効率的に解きうる事を示す.ここでの目的は最短路長さの分布関数B^^〜_G(x)を記述する数式を,xの多項式や指数関数の積の和として出力する事を行う.ここで,もし与えられたグラフGの木幅(treewidth)が定数k以下で各枝長さが互いに独立で期待値1の指数分布に従うならば,提案手法はグラフの規模の多項式時間で完了する事を示す.
2012-03-09

著者

関連論文

スポンサーリンク