線形ネットワークにおける時間複雑度と通信複雑度が共に最適な分散ソーティング
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 最適な時間複雑度の実現を目指して線形ネットワークにおける分散ソーティングアルゴリズムを構築し, その時間複雑度と通信複雑度が共に最適であることを証明する.ソーティングは基本かつ重要な問題のひとつであるため, 分散アルゴリズムも研究されている.本研究では, 従来の通信複雑度を重視した研究とは異なり, 厳密に最適な時間複雑度を実現するアルゴリズムの構築を目指している.この方針に基づいて既にひとつのアルゴリズムを構築しているが, 拡張した問題に対しては時間最適性が保証されない.そこで本稿では, それとは別のアイデアを用いて時間最適なアルゴリズムを構築する.その結果, 時間複雑度だけでなく通信複雑度も最適にすることができた.また, 拡張した問題にも適用することを示す.
- 社団法人電子情報通信学会の論文
- 2000-07-18
著者
関連論文
- 線形ネットワークにおける時間複雑度と通信複雑度が共に最適な分散ソーティング
- 線形ネットワークにおける最適な通信複雑度の分散ソーティングアルゴリズム(組み合わせ最適化(3))
- 線形ネットワークにおける逐次・並列ソーティングの概念に基づいた分散ソーティング (新しいパラダイムとしてのアルゴリズム工学)
- 線形ネットワークにおける時間複雑度を重視した分散ソーティングアルゴリズム(グラフ・ネットワーク(1))
- タスクの公平性を考慮レた大域的タスク割当手法の提案(トラヒック,一般)
- 単方向リングにおける分散資源割当アルゴリズム