Partitioning graphs to speed up point-to-point shortest path computations

Computing the shortest paths in graphs is a fundamental problem with numerous applications. The rapid growth of network in size and complexity has made it necessary to decrease the execution time of the shortest path algorithm. We develop an effective graph partition method to retrieve Balanced Traversing Distance partitions and constitute a hierarchical graph model based on the decomposed network for accelerating the path queries. We then propose a new heuristic hierarchical routing algorithm that can significantly reduce the search space by pruning unpromising subgraph branches. We evaluate our approach experimentally under different network partition schemes to show the gain in performance.