Title :
A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting
Author :
Tang, Yuxin ; Zhang, Yunquan ; Chen, Hu
Author_Institution :
Lab. of Parallel Comput., Chinese Acad. of Sci., Beijing
Abstract :
In this paper, we focus on satisfying the actual demands of quickly finding the shortest paths over real-road networks in an intelligent transportation system. A parallel shortest path algorithm based on graph partitioning and iterative correcting is proposed. After evaluating the algorithm using three real road networks, we conclude that our graph-partitioning and iterative correcting based parallel algorithm has good performance. In addition, it achieves more than a 15-fold speedup on 16 processors in an IBM cluster over these real road networks.
Keywords :
automated highways; graph theory; iterative methods; parallel algorithms; traffic engineering computing; transportation; graph-partitioning; intelligent transportation system; iterative correction; parallel shortest path algorithm; real-road network; Clustering algorithms; Intelligent networks; Intelligent transportation systems; Iterative algorithms; Laboratories; Parallel algorithms; Parallel processing; Partitioning algorithms; Roads; Tree graphs; graph partitioning; intelligent transportation; parallel computing; parallel shortest path algorithm;
Conference_Titel :
High Performance Computing and Communications, 2008. HPCC '08. 10th IEEE International Conference on
Conference_Location :
Dalian
Print_ISBN :
978-0-7695-3352-0
DOI :
10.1109/HPCC.2008.113
