A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths

• Item type: Journal(1)
• 公開日: 1996-09-15
• タイトル: A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
• タイトル / 言語: en
• タイトル: A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: Department of Computer Software The University of Aizu
• 著者所属: Department of Computer Science University of Ibaraki
• 著者所属(英): en
• 著者所属(英): Department of Computer Software, The University of Aizu
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Ibaraki
• 著者名: Qian-PingGu; Tadao, Takaoka
• 著者名(英): Qian-Ping, Gu; Tadao, Takaoka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper presents a parallel algorithm that computes the single source longest path problem on acyclic graphs G(V A) with integer arc lengths on SIMD-SM-EREW parallel computers. The algorithm solves the problem in O(log^2(ln)) time O((ln)^<2.376>) processors and O((ln)^2) memory space where n = |V| and the arc lengths are integers in the set {1 2 ... l}.For any constant l our algorithm solves the single source longest path problem in O(log^2 n)time O(n^<2.376>) processors and O(n^2) memory space. Our algorithm is then used to derive O(log^2 n) time O(n^<2.376>) processors and O(n^2) memory space parallel algorithms for a number of problems such as minimum coloring maximum clique and so on of permutation graphs on an SIMD-SM-EREW computer.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a parallel algorithm that computes the single source longest path problem on acyclic graphs G(V,A) with integer arc lengths on SIMD-SM-EREW parallel computers. The algorithm solves the problem in O(log^2(ln)) time, O((ln)^<2.376>) processors, and O((ln)^2) memory space, where n = |V| and the arc lengths are integers in the set {1,2,...,l}.For any constant l, our algorithm solves the single source longest path problem in O(log^2 n)time, O(n^<2.376>) processors, and O(n^2) memory space. Our algorithm is then used to derive O(log^2 n) time, O(n^<2.376>) processors, and O(n^2) memory space parallel algorithms for a number of problems, such as minimum coloring, maximum clique, and so on, of permutation graphs on an SIMD-SM-EREW computer.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 37, 号 9, p. 1631-1636, 発行日 1996-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764