WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 11, 2012
Re-Optimizing the Performance of Shortest Path Queries Using Parallelized Combining Speedup Technique based on Bidirectional Arc Flags and Multilevel Approach
Authors: ,
Abstract: Globally shortest path problems have increasing demand due to voluminous datasets in applications like roadmaps, web search engines, mobile data sets, etc., Computing shortest path between nodes in a given directed graph is a very common problem. Among the various shortest path algorithms, Dijkstra’s shortest path algorithm [1] is said to have better performance with regard to run time than the other algorithms. The output of Dijkstra’s shortest path algorithm can be improved with speedup techniques. In this paper a new combined speedup technique based on three speedup techniques were combined and each technique is parallelised individually and the performance of the combination is measured with respect to pre-processing time, runtime and number of nodes visited in random graphs, planar graphs and real world data sets.
Search Articles
Keywords: Bidirectional Arcflags, Multilevel method, Multilevel Arcflags, Parallelized Multilevel Arcflags