| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-09-20 13:15 Approximating the Distribution Function of Minimum Spanning Tree Cost with Normally Disributed Stochastic Edge Weights ○Ei Ando・Hirotaka Ono・Kunihiko Sadakane・Masafumi Yamashita（Kyushu Univ.）  COMP2007-35 |
|
| 抄録 | （和） | 本稿では，ある与えられた$n$頂点グラフ$G$の枝重みが，互いに独立で正規分布に従う確率変数として 与えられる場合を考え，そのグラフ上での確率的な最小全域木問題を考える． 最小全域木のコストもまた確率変数であるが，その分布関数$F_{\rm MST}(x)$を記述することは 自明ではない．本稿においては$O({\rm MST}(G)+m+n\log n)$時間で最小全域木のコストの分布関数を 近似する手法を示す．ただし，$m$は$G$の枝の数であり， ${\rm MST}(G)$は確定的な枝重みをもつグラフにおいて最小全域木を求めるのにかかる時間である． グラフ$G$の全ての全域木の集合を$\STs$とする． アルゴリズムの出力$\tilde F(x)$は，$\tilde F(x)\le 1-2^{-|\cal{T}|}$を満たす$x$について $F_{\rm MST}(x)$の上限を与え，さらに枝重みの分散のうち最大のものを$\sigma^2$とすると $0< a\le 1-2^{-|\cal{T}|}$に関して $|F_{\rm MST}^{-1}(a)-\tilde F^{-1}(a)|=o(n\sigma\sqrt{\log n})$を満たす． |
| （英） | Given a graph $G$ of $n$ vertices whose edge weights are random variables and obey mutually independent normal distributions, we consider a stochastic minimum spanning tree problem. The weight of the minimum spanning tree is also a random variable, but its distribution function $F_{\rm MST}(x)$ cannot be represented by a simple distribution function in general. We show an algorithm, whose output is a approximation function $\tilde F(x)$ of the distribution function of stochastic minimum spanning tree weight. Its running time is $O({\rm MST}(G) + m + n\log n)$, where $m$ is the number of edges in $G$ and ${\rm MST}(G)$ is the time complexity of the (deterministic) minimum spanning tree weights. Let $\cal{T}$ be the family of all spanning trees in $G$. $\tilde F(x)$ gives an upper bound on $F_{\rm MST}(x)$ for $x$ such that $\tilde F(x)\le 1-2^{-|\cal{T}|}$, and $\tilde F(x)$ satisfies that $|F_{\rm MST}^{-1}(a)-\tilde F^{-1}(a)|=o(n\sigma\sqrt{\log n})$ for $0< a \le 1-2^{-|\cal{T}|}$ where $\sigma^2$ is the maximum variance of edge weights. |
|
| キーワード | （和） | 最小全域木 / 確率的な枝重み / 正規分布 / / / / / |
| （英） | Minimum spanning tree / Stochastic edge weight / Normal distribution / / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 219, COMP2007-35, pp. 21-27, 2007年9月. | |
| 資料番号 | COMP2007-35 | |
| 発行日 | 2007-09-13 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-35 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2007-09-20 - 2007-09-20 |
| 開催地（和） | 豊橋技術科学大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2007-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Approximating the Distribution Function of Minimum Spanning Tree Cost with Normally Disributed Stochastic Edge Weights |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最小全域木 / Minimum spanning tree |
| キーワード(2)（和/英） | 確率的な枝重み / Stochastic edge weight |
| キーワード(3)（和/英） | 正規分布 / Normal distribution |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 安藤 映 / Ei Ando / アンドウ エイ |
| 第1著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第2著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 定兼 邦彦 / Kunihiko Sadakane / サダカネ クニヒコ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 山下 雅史 / Masafumi Yamashita / ヤマシタ マサフミ |
| 第4著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-09-20 13:15:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-35 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.219 |
| ページ範囲 | pp.21-27 |
| ページ数 | 7 |
| 発行日 | 2007-09-13 (COMP) |
[研究会発表申込システムのトップページに戻る]