並列トポロジカル整列アルゴリズム(計算科学と数値シミュレーションの理論と実践)
スポンサーリンク
概要
- 論文の詳細を見る
無閉路有向グラフDAG (Directed Acyclic Graph)において節点数n,辺数mとするとき,節点のトポロジカル整列を求める従来の並列アルゴリズムは. CROW-PRAM計算機モデルでΟ(n^3)個のプロセッサを用いて,Ο(log n)時間で実行するアルゴリズムがある.このアルゴリズムは推移的閉包行列の計算に依存しているので,Ο(n^3)個のプロセッサを減少させることは難しい.本橋では,CREW-PRAM計算機モデルのもとで. DAG上における効率良い並列トポロジカル整列アルゴリズムを提案する.提案する並列アルゴリブムは分割統治法によるアルゴリズムの設計法をもとに,基本的な並列アルゴリズムのみを用いて設計される.具体的にはい,まじめにDAGを入出次数がたかだか1の節点からなる線形リストに分割し,次に再帰的に線形リストを併合しながら各節点の最大ランク値を求める.最後に,最大ランク値をもとに節点のトポロジカル整列を行う並列アル'ゴリズムである.この提案するアルゴリズムの計算量はCREW-PRAM計算機モデルでプロセッサ数がΟ(n+m),計算時間がΟ(1og^2m)である.
- 一般社団法人情報処理学会の論文
- 2004-04-15
著者
-
多田 昭雄
崇城大学情報学部コンピュータシステムテクノロジー学科
-
中村 良三
熊本大学工学部
-
右田 雅裕
熊本大学総合情報基盤センター
-
中村 良三
熊本大学工学部数理情報システム工学科
-
中村 良三
熊本大学工学部電気情報工学科
-
多田 昭雄
崇城大学工学部
-
多田 昭雄
崇城大学 情報学部
関連論文
- 無向グラフにおいて1つのオイラー小径を求める並列アルゴリズム
- 電子新聞に対する動的クラスタリング手法の提案
- 個人属性を考慮した情報フィルタリング
- ユーザの好みを考慮した新聞記事のランキング
- マルチエージェントによる新聞記事のランキング方式の提案
- オンラインJava applet演習環境の開発と実践
- 全学必修科目「情報基礎A」「情報基礎B」の大規模強調授業
- LMSを用いた学期末試験としての一斉オンラインテスト
- 〔熊本大学〕全学無線LANシステムによるユビキタス環境の構築
- コストに配慮したキャンパス全域ギガビットネットワーク
- 線形法における探索アルゴリズムの解析
- 分離連鎖法における挿入・探索アルゴリズムの解析
- キャッシュコヒーレンスプロトコルにおけるオーナーシップに関する考察
- キャッシュコヒーレンスプロトコルに対する一考察
- PERTチャートにおけるクリティカルパスを求める並列アルゴリズム(アルゴリズム理論)
- 3U-4 統計的手法によるネットワーク利用可能帯域の推定と予測
- ニュ-ラルネットワ-クによる回転パタ-ンの学習認識
- 入れ子構造を許す言語処理で用いる名前表の一構成法とその解析
- 線形法におけるパケット方式を用いたときのアクセス回数について
- 分離連鎖法におけるバケット方式を用いたときのアクセス回数について
- 見出しの探索頻度を考慮した探索路長の考察
- 分散記憶法における探索頻度を考慮した探索路長とその評価
- リスト FORTRAN とそのプリプロセッサ
- 任意に回転したパターンと回転角度を認識する複写学習モデル
- 位置ずれ・回転パターンを認識するニューラルネットワーク
- JavaによるLANシミュレータの実現
- JavaによるLANシミュレータの実現
- SNMPによるネットワーク不正アクセス検出エージェントの実現
- オブジェクト指向によるLAN構築支援システムの設計
- Microprogrammed E-MIXによるアセンブリ言語教育支援システムの設計と開発
- 結合グラフ証明手続きにおける効率的な探索戦略
- 2分探索木における探索アルゴリズムの解析
- 線形ハッシュ法における探索アルゴリズムの解析
- 並列トポロジカル整列アルゴリズム(計算科学と数値シミュレーションの理論と実践)
- DAGの最長路を求める並列アルゴリズム
- 有向グラフの強連結成分を求める並列アルゴリズム
- 並列トポロジカル整列アルゴリズム
- 2分探索木を平衡化する並列アルゴリズム
- マルチプロセッサシステムにおける並列タスクスケジューリングについての一考察
- 2分探索木を通りがけ順になぞる並列アルゴリズム
- 有向グラフの最長路を求める効率良い並列アルゴリズム
- 疎な有向グラフの強連結成分を求める効率良い並列アルゴリズム
- 回転パターンを自動生成するニューラルネットワーク
- 2分探索木における挿入・探索アルゴリズムの解析
- 入れ子構造を許す言語処理で用いる名前表の一構成法とその解析
- 4年間にわたる情報処理科目アンケート結果の分析と考察