正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法

スポンサーリンク

概要

論文の詳細を見る
本稿では,ある与えられたn頂点グラフGの枝重みが,互いに独立で正規分布に従う確率変数として与えられる場合を考え,そのグラフ上での確率的な最小全域木問題を考える.最小全域木のコストもまた確率変数であるが,その分布関数F_<MST>(x)を記述することは自明ではない.本稿においてはO(MST(G)+m+nlogn)時間で最小全域木のコストの分布関数を近似する手法を示す.ただし,mはGの枝の数であり,MST(G)は確定的な枝重みをもつグラフにおいて最小全域木を求めるのにかかる時間である.グラフGの全ての全域木の集合をTとする.アルゴリズムの出力F(x)は,F(x)≦1-2^<-|T|>を満たすxについてF_<MST>(x)の上限を与え,さらに枝重みの分散のうち最大のものをσ^2とすると0<a≦1-2^<-|T|>に関して|F^<-1>_<MST>(a)-F^<-1>(a)|=o(nσ√<logn>)を満たす.
2007-09-13

著者

関連論文

もっと見る

スポンサーリンク