2分木の平衡分解木を求めるコスト最適な並列アルゴリズム(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
2分木Tから1辺を取り除くと, Tは二つの部分木T_1, T_2に分割される.この操作をT_1, T_2それぞれに対し再帰的に行うことによって, 木は最後には一つひとつの頂点まで分割される.この分割の過程を表現した木をTの分解木という.この分割過程において, 任意の分割によって得られた二つの木の頂点数の比がある定数以下であるとき, 得られたTの分解木を平衡分解木という.本論文では, n頂点2分木の平衡分解木を, O(log n)時間, n / log nプロセッサで求めるコスト最適なCREW PRAM上の並列アルゴリズムを示す.また, このアルゴリズムを応用し, 単純多角形の最小凸分割の近似解についてもコスト最適な並列アルゴリズムが得られることを示す.
- 社団法人電子情報通信学会の論文
- 2000-01-25
著者
-
陳 慰
名古屋工業大学
-
藤原 暁宏
九州工業大学大学院情報工学研究院
-
都倉 信樹
大阪大学基礎工学部情報工学科
-
都倉 信樹
鳥取環境大学環境情報学部情報システム学科
-
増澤 利光
奈良先端科学技術大学院大学情報科学研究科
-
陳 慰
名古屋工業大学電気情報工学科
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 入力誤差を反映したボロノイ領域(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- D-6-2 PRAM型並列計算機メモリユニットの設計と実現
- COMP2000-22 分散環境に適した行列積アルゴリズムについて
- D-1-11 非同期膜計算による充足可能性問題とハミルトン路問題の解法(D-1.コンピュテーション,一般セッション)
- ソート集合のある分割に対する並列アルゴリズムについて
- 「アクレディテーション」
- ユーザのアクセスコストを最小化するハイパーテキストの構成法
- 大きい目標の選択操作に対するFittsの法則の適合性
- アクセスコストを最小化するハイパーテキストの構成法
- アクセスコストを最小化するハイパーテキストの構成法
- 実験環境と実使用環境における目標選択動作の比較
- 大きい目標の選択操作に対するFittsの法則の適合性の評価
- 最適メニュー階層構造を求めるアルゴリズムについて
- 最適メニューシステムの設計法について
- 最適なメニュー階層構造を求めるアルゴリズム
- Fittsの法則に基くマウスの操作方向の効率への影響
- 5X-6 情報教育のための教育基本ソフトウェア・電子教材・教育支援プロジェクト
- 衝突検出機構のないマルチアクセスチャネルでの自己安定リーダ選択アルゴリズム(計算量理論とアルゴリズム論文小特集)
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム(並列・分散)
- マルチアクセスチャネルを利用した自己安定リーダ選択アルゴリズムの改良
- マルチアクセスチャネルを利用した自己安定リーグ選択アルゴリズム
- 分散システムにおける大域条件式成立の可能性検出
- 移動ネットワークを含む分散システムとその上のスナップシヨット・アルゴリズム
- マルチアクセスチャネル上での自己安定リーダ選択アルゴリズム
- DNA計算における対数時間ソートアルゴリズム
- 拡張されたヒープ領域管理機能をもつ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),教材の開発)
- ヘテロジニアスBSPモデル上の2次元データ分割
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- 星状多角形内の同期式自律分散ロボットの一点集合問題
- 2連結グラフに対するATM網に適した最適な耐故障性ルーティング
- 点集合の強凸-包含を求めるアルゴリズム
- スーパーキューブの耐故障性について
- 異なる半径の数を限定した円集合の凸包を求める最適並列アルゴリズム
- 誤差耐性のある強凸包構成問題に対する並列解法
- 円集合の凸包を求める効率の良い並列アルゴリズム
- D-1-2 GRID 環境に適した効率の良い完全交換アルゴリズム
- 膜計算における基本演算アルゴリズム
- 検知領域交点を考慮した連結センサカバーアルゴリズム
- DNA計算による浮動小数点演算アルゴリズム
- 最小スループット制御を行うアクセスポイント選択手法
- A-006 局所探索を用いた集中型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-005 DNA計算におけるMAX-SATの解法(A分野:モデル・アルゴリズム・プログラミング)
- A-004 重み付けを用いた分散型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-003 DNA計算における乗算および除算アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- DNA計算における対数時間ソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- A-017 グリッド環境における完全交換に対するスケジューリングアルゴリズム(A.モデル・アルゴリズム・プログラミング)
- A-008 組み合わせ最適化アルゴリズムに基づく研究室配属システムの開発(A.モデル・アルゴリズム・プログラミング)
- A-003 DNAを用いた0-1整数計画問題の解法(A.モデル・アルゴリズム・プログラミング)
- Procedures for Multiple Input Functions with DNA Strands (Evolutionary Advancement in Fundamental Theories of Computer Science)
- D-1-4 DNA 計算における最大値計算および辞書演算
- 2値画像の重みつき距離変換を行なう並列アルゴリズム
- P-完全問題に対する幾つかの多項式的に加速する並列アルゴリズム
- D-1-7 Polynomially fast parallel algorithms for some P-complete problems
- Cost optimal parallel algorithms for $P$-complete problems (Algorithm Engineering as a New Paradigm)
- COMP2000-20 DNA計算におけるグラフ問題の符号化について
- D-1-4 抑制性ニューロンを用いたSN Pシステムにおける素因数分解(D-1.コンピュテーション,一般セッション)
- COMP2000-21 κ-連結グラフに対する小さなルーティングテーブルを持つ最適な耐故障性ルーティング
- 不完全情報環境下における時系列データと仮説推論による行動決定 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 平面的グラフの基無指定k-分割問題に対する線形時間アルゴリズム
- 2分木の平衡分解木を求めるコスト最適な並列アルゴリズム(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- ペイシェンス・ソートおよび最長昇順部分列問題に対するコスト最適な並列アルゴリズム
- スタックを用いた幅優先探索に関する並列アルゴリズム
- 辞書式順極大3和問題に対するBSPモデル上のコスト最適な並列アルゴリズム
- ソート点集合の凸包を求める定数通信ラウンドの並列アルゴリズム
- P完全問題に対するBSPモデル上の並列アルゴリズム
- JSPP '99参加報告(学術会合報告)
- P完全問題の実用的な並列性について
- メッシュ上でユークリッド距離変換を行う並列アルゴリズム
- 円集合の凸包を求める並列アルゴリズム
- PRAMのハードウェア化に関する設計と実現
- 平面セグメントの上エンベロプを求める並列アルゴリズム
- 濃淡画像の連結成分を求める並列アルゴリズム
- 3連結平面的グラフに対する最適な耐故障性ルーティング