確率的な通信時間を持つネットワークにおけるブロードキャスト時間の計算手法
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,計算機ネットワークにおいて各計算機を互いに接続する通信路でのメッセージ伝達にかかる時間 (通信時間) がランダムな時間がかかるものと考えた場合に,そのネットワーク内でのブロードキャストにかかる時間の分布関数を計算する方法を考える.各通信路の通信時間は互いに独立な確立変数とする.本稿ではまずこの問題が #P -完全であることを証明し,その後ブロードキャスト時間の分布関数を計算するアルゴリズム BC-PDF について述べる.BC-PDF は一般のグラフにおいてはネットワーク規模について指数的な処理時間が必要であるものの、最大極小カットのサイズが定数 k で抑えられるようなネットワークで,各枝重みが分散 1 の指数分布に従う場合,グラフ規模の多項式時間で計算を完了する.
- 2011-02-28
著者
-
Ei Ando
Faculty of Computer and Information Science, Sojo University
-
Joseph Peters
School of Computing Science, Simon Fraser University
-
Ei Ando
Faculty Of Computer And Information Science Sojo University
-
Joseph Peters
School Of Computing Science Simon Fraser University