Parallel graph algorithm

• Main Author: Nguyen, Duc Hieu.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/48790
• Institution: Nanyang Technological University

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.