著者

右田 雅裕 多田 昭雄 中村 良三

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.538, pp.9-16, 2003-12-15

---

本橋では,CREW-PRAM並列計算機モデルのもとで,DAG (Directed Acyclic Graph)の最長路を求める効率よい並列アルゴリズムを提案する.また,従来の推移的閉包行列の計算方法を用いない並列トポロジカル整列アルゴリズムを示し,これを用いて最長路を求める並列アルゴリズムである.具体的には,はじめにDAGのトポロジカル整列を行い節点のランクを求め,次にその逆向き線形リストに対して同様の方法でランクを求めて,これらのランクを用いてすべての最長路を求める並列アルゴリズムである.DAGにおいて節点数n,辺数mとすると,提案するアルゴリズムの計算量はCREW-PRAM並列計算機モデルでプロセッサ数がO(n+m),時間量がO(log^2m)である.