| Presentation | 2003/12/15 Paralell Algorithm for finding Longest Paths in a Directed Acyclic Graph Masahiro MIGITA, Akio TADA, Ryozo NAKAMURA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we propose an efficient paralell algorithm for finding longest paths in a DAG (directed acyclic graph), based on a CREW-PRAM model. In addition to this, we also show a parallel topological sorting algorithm, that does not depend on the transitive closure matrix calculation, and apply this algorithm to that one. The proposed algorithm at first makes a topological sorting for a given DAG merging its linked lists, and get a rank of each vertex. Next, in the same way, it get a rank of each vertex for its riversal directed linked lists, finally the longest paths are found in a given DAG. In a DAG with the number of vertices n and the number of edges m, the proposed algorithm requires O(n+m) processors and O(log^2m) times on a CREW-PRAM model. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | DAG / longest path / parallel algorithm |
| Paper # | COMP2003-63 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2003/12/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Paralell Algorithm for finding Longest Paths in a Directed Acyclic Graph |
| Sub Title (in English) | |
| Keyword(1) | DAG |
| Keyword(2) | longest path |
| Keyword(3) | parallel algorithm |
| 1st Author's Name | Masahiro MIGITA |
| 1st Author's Affiliation | Center for Multimedia and Information Technologies, Kumamoto University() |
| 2nd Author's Name | Akio TADA |
| 2nd Author's Affiliation | Faculty of Engineering, Sojo University |
| 3rd Author's Name | Ryozo NAKAMURA |
| 3rd Author's Affiliation | Faculty of Engineering, Kumamoto University |
| Date | 2003/12/15 |
| Paper # | COMP2003-63 |
| Volume (vol) | vol.103 |
| Number (no) | 538 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |