Parallel graph algorithm
This report records the author’s work during the project’s period. This project will study parallel graph algorithm for solving graph based problem. It will research the shortest path problems and all shortest path problems. The author studied some well-known algorithms such...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/48790 |
| _version_ | 1811684746902634496 |
|---|---|
| author | Nguyen, Duc Hieu. |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Nguyen, Duc Hieu. |
| author_sort | Nguyen, Duc Hieu. |
| collection | NTU |
| description | This report records the author’s work during the project’s period. This project will study
parallel graph algorithm for solving graph based problem. It will research the shortest
path problems and all shortest path problems.
The author studied some well-known algorithms such as Dijiskstra algorithm and Floyd
algorithm. They have been studied in sequential, parallel with shared memory and
distributed memory. After that the author ran a benchmark for Floyd algorithm with
distributed memory to analyze it further.
After studied the shortest path problems, the author came up with a new approach which
used Floyd algorithm in order to reduce the number of cycles which needs to complete
the calculation for all shortest path problem. The author applied the knowledge about
parallel processing and graph problem to complete the study.
The report highlights what the author did and learnt during the final year project’s
period. |
| first_indexed | 2024-10-01T04:33:32Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/48790 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:33:32Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | ntu-10356/487902023-03-03T20:52:55Z Parallel graph algorithm Nguyen, Duc Hieu. School of Computer Engineering Parallel and Distributed Computing Centre Suhaib A Fahmy DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity This report records the author’s work during the project’s period. This project will study parallel graph algorithm for solving graph based problem. It will research the shortest path problems and all shortest path problems. The author studied some well-known algorithms such as Dijiskstra algorithm and Floyd algorithm. They have been studied in sequential, parallel with shared memory and distributed memory. After that the author ran a benchmark for Floyd algorithm with distributed memory to analyze it further. After studied the shortest path problems, the author came up with a new approach which used Floyd algorithm in order to reduce the number of cycles which needs to complete the calculation for all shortest path problem. The author applied the knowledge about parallel processing and graph problem to complete the study. The report highlights what the author did and learnt during the final year project’s period. Bachelor of Engineering (Computer Science) 2012-05-09T06:29:03Z 2012-05-09T06:29:03Z 2012 2012 Final Year Project (FYP) http://hdl.handle.net/10356/48790 en Nanyang Technological University 63 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity Nguyen, Duc Hieu. Parallel graph algorithm |
| title | Parallel graph algorithm |
| title_full | Parallel graph algorithm |
| title_fullStr | Parallel graph algorithm |
| title_full_unstemmed | Parallel graph algorithm |
| title_short | Parallel graph algorithm |
| title_sort | parallel graph algorithm |
| topic | DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity |
| url | http://hdl.handle.net/10356/48790 |
| work_keys_str_mv | AT nguyenduchieu parallelgraphalgorithm |