確率的な枝重みつき無向グラフ上の二点間最短路長さ分布の近似計算手法

• Item type: SIG Technical Reports(1)
• 公開日: 2012-01-21
• タイトル: 確率的な枝重みつき無向グラフ上の二点間最短路長さ分布の近似計算手法
• タイトル / 言語: en
• タイトル: Approximating the Stochastic Shortest Path Length Between Two Vertices
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Faculty of Computer and Information Science, Sojo University
• 著者所属: School of Computing Science, Simon Fraser University, Burnaby, Canada.
• 著者所属(英): en
• 著者所属(英): Faculty of Computer and Information Science, Sojo University
• 著者所属(英): en
• 著者所属(英): School of Computing Science, Simon Fraser University, Burnaby, Canada.
• 著者名: Ei, Ando; Joseph, Peters
• 著者名(英): Ei, Ando; Joseph, Peters
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，無向グラフ G における二点間の確率的な最短路長さの分布関数 BG(x) に対する近似アルゴリズムを提案する．確率的な最短路問題は厳密に解く事が困難なことが多く，枝長さが二つの離散的な値を取り得るような場合，最短路長さの確率分布を求める問題は #P-完全である．一方で，枝長さの分布とグラフの構造の両方に良い性質がある場合には確率分布関数 BG(x) を効率的に計算できる．本稿では，二点間の確率的な最短路問題の分布関数を求める問題について，まず枝長さが二値分布に従う場合にこの問題が#P-完全であることを示す．次に，連続的な分布に従う枝長さを考え，それらがある自然な条件を満たし，かつグラフ G の treewidth が定数k以下である場合を考える．このときxの多項式 BG(x) として BG(x) を近似することを考え，ある正の実数 ε,wが与えられるとき，|BG(x)-BG(x)| ≤εを 0≤x≤w の範囲で満たすような x を，x の上限 w，枝の数 m，許容誤差の逆数 1/ε の多項式時間で BG(x) を計算できる事を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an approximation algorithm for computing the distribution function BG(x) of the stochastic shortest path length between two vertices in undirected graph G. The stochastic shortest path problem is hard to solve; computing the exact stochastic shortest path lengths' distribution function is #P-complete if we assume that the edge lengths can take two discrete values. We show that, however, if we consider some continuously distributed edge lengths satisfying some natural conditions, we can approximately compute the distribution function BG(x) of the stochastic shortest path length of G. Our approximation algorithm outputs a polynomial BG(x) that approximates BG(x) for 0≤x≤w and satisfies that |BG(x)-BG(x)|≤ε, where w and ε are positive values. The running time of our algorithm is polynomial in the graph size, w and 1/ε if G has a constant treewidth k.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2012-AL-138, 号 8, p. 1-8, 発行日 2012-01-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会