完全ネットワークでの最小重み生成木構成分散問題のビット複雑度について
スポンサーリンク
概要
- 論文の詳細を見る
ある問題を解くのに必要な情報がネットワークで結合されている複数台のプロセッサに分散してしまっている状況で,それらのプロセッサがメッセージを用いて情報交換し,その問題(分散問題)を解くアルゴリズムは分散アルゴリズムと呼ばれる.本論文では,完全ネットワークでの最小重み生成木構成分散アルゴリズムに関して考察する.完全ネットワークでの最小重み生成木構成分散問題に関しては,これまでに,メッセージ複雑度がΘ(n^2)であること,ビット複雑度の上界がO(n^2logn+wnlogn),下界がΩ(n^2)が知られている(最悪時評価,n:プロセッサ数,w:リンクの重みを表すのに必要なビット数).本論文では,ビット複雑度の上界がO(n^2+wnlogn)であることを示す.この結果は,w=O(n/logn)の場合,O(n^2)となり,下界とオーダ的に一致する.
- 社団法人電子情報通信学会の論文
- 1993-07-25
著者
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 共有メモリシステムにおける調停木スキップ相互排除アルゴリズム
- 入力誤差を反映したボロノイ領域(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- BISTにおける高品質遅延故障テストのためのシード選択法(遅延故障テスト,VLSI設計とテスト及び一般)
- C素子スキャンパスを用いた非同期式順序回路に対する完全スキャン設計法(設計/テスト/検証)
- 「アクレディテーション」
- ユーザのアクセスコストを最小化するハイパーテキストの構成法
- 大きい目標の選択操作に対するFittsの法則の適合性
- アクセスコストを最小化するハイパーテキストの構成法
- アクセスコストを最小化するハイパーテキストの構成法
- 実験環境と実使用環境における目標選択動作の比較
- 大きい目標の選択操作に対するFittsの法則の適合性の評価
- 最適メニュー階層構造を求めるアルゴリズムについて
- 最適メニューシステムの設計法について
- 最適なメニュー階層構造を求めるアルゴリズム
- Fittsの法則に基くマウスの操作方向の効率への影響
- 5X-6 情報教育のための教育基本ソフトウェア・電子教材・教育支援プロジェクト
- 衝突検出機構のないマルチアクセスチャネルでの自己安定リーダ選択アルゴリズム(計算量理論とアルゴリズム論文小特集)
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム(並列・分散)
- マルチアクセスチャネルを利用した自己安定リーダ選択アルゴリズムの改良
- マルチアクセスチャネルを利用した自己安定リーグ選択アルゴリズム
- 分散システムにおける大域条件式成立の可能性検出
- 移動ネットワークを含む分散システムとその上のスナップシヨット・アルゴリズム
- マルチアクセスチャネル上での自己安定リーダ選択アルゴリズム
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- 「JABEEの発足と情報処理学会アクレディテーション委員会活動」
- 再構成アレー上の接頭部和問題について
- 再構成アレイ上で接頭部和を求めるアルゴリズムについて
- ミニコンピュータ複合体とそのオペレーティング・システム
- マウスとペンの操作精度の比較
- 情報教育に何が一番必要か
- 7-104 学科内全講義のビデオ撮影・蓄積・配信への取り組み((9)e-ラーニング実践-I)
- (225)遠隔ペアプログラミング支援システムSATORIの開発とプログラミング教育への適用(セッション64 e-ラーニング(インターネット・マルチメディア利用教育を含む)V)
- (135)教員の作業効率向上を目指した授業支援システムの構築と運用(セッション39 教育システムA(講義・演習)IX)
- (96)大学内でのアンケートシステムの運用事例と考察(セッション28 教育評価・自己点検・評価システムIV)
- 学生による講義ビデオのしおり付け実験の報告
- 授業内の学生の反応を記録・解析するシステムの運用報告
- (148)Javaを導入言語としたプログラミング教育(第39セッション 教育研究指導(III))
- (134)鳥取環境大学における学生ノートPCを活用した情報処理教育(第36セッション 教育システム(講義・演習)(VII),教材の開発)
- (52)情報数学導入科目の一つの構想と実施経験(第14セッション 教材の開発(II))
- (15)生徒と教師の授業時間内のやりとりを支援するシステムの実装と評価(第4セッション 教育システム(講義・演習)(IV))
- 合同な点クラスタに対する点クラスタボロノイ図の構成
- 入力誤差を反映したボロノイ領域
- 入力誤差を反映した凸包問題とその解法(計算量理論とアルゴリズム論文小特集)
- 入力誤差を考慮した凸包問題
- 入力が誤差を含む場合の厳密な交差判定
- 計算機演習室におけるGUI操作履歴の収集と解析
- GUIにおける実操作履歴の取得とその意図分析
- 2本の平行線間へのチェインの配置問題
- 入力誤差をAffine Arithmeticで表現した交差判定問題
- 2本の平行線間へのチェインの配置問題
- 多角形内での2-リンクアームの到達可能性判定問題
- 点集合の移動に関する最短経路問題について
- 直交順序を保存する方形の最小面積非交差再配置問題
- 直交順序を保存する矩形の非交差再配置問題について
- 非パイプラインプロセッサの命令レベル自己テストのためのテスト容易化設計(上流DFT,VLSI設計とテスト及び一般)
- 縮退故障とパス遅延故障のためのプロセッサの命令レベル自己テスト法(LSIのテスト・診断技術論文)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- プロセッサ自己テストのためのコントローラ入力時相空間制約(VLSI設計とテスト)
- データフローを考慮したプロセッサ自己テストのためのテンプレート生成(VLSI設計とテスト)
- 分散移動システムにおけるスナップショット・アルゴリズム
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- 故障推定機能を利用した永久故障に耐性のある自己安定プロトコル
- テスト実行時の温度均一化のためのテストパターン並び替え法(Iddqテスト・温度均一化,VLSI設計とテスト及び一般)
- RTLパス数最小化のためのリソースバインディング法(スキャンテスト・テスト容易化高位合成,VLSI設計とテスト及び一般)
- Cost optimal parallel algorithms for $P$-complete problems (Algorithm Engineering as a New Paradigm)
- 共有メモリシステム上でスナップショット問題を解く分散アルゴリズム
- 超立方体状ネットワークでの最小重み生成木構成分散問題のメッセージ複雑度について
- 完全ネットワークでの最小重み生成木構成分散問題のビット複雑度について
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非同期共有メモリシステムにおける適応型繰り返し改名アルゴリズム
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合せプロトコル(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 線形化可能な分散共有メモリの無待機な実現 (新しいパラダイムとしてのアルゴリズム工学)
- 線形化可能性を保証する分散共有メモリの無待機な実現
- 線形化可能性を保証する共有オブジェクトの無待機な実現
- 共有メモリシステムにおける同期時間最適な自己安定無待機時計合わせプロトコル
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合わせプロトコル
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合わせプロトコル
- 弱可検査性を考慮したデータパスの高位合成
- 分散移動システムにおける全域チェックポイントについて
- 高位合成情報を用いたRTLフォールスパス判定(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平衡構造を利用した安全なスキャン設計(スキャンテスト,VLSI設計とテスト及び一般)
- プロセッサの命令レベル自己テストのためのテスト容易化設計(集積回路技術とアーキテクチャ技術の協調・融合へ向けた,プロセッサ,並列処理,システムLSIアーキテクチャ及び一般)
- プロセッサの命令レベル自己テストのためのテスト容易化設計(集積回路技術とアーキテクチャ技術の協調・融合へ向けた,プロセッサ,並列処理,システムLSIアーキテクチャ及び一般)
- 階層BIST : 低オーバヘッドを実現するTest-per-clock BIST