An Efficient Route Computation Approach for Large Graphs
The problem of efficient routing arises in several applications such as transportation problems and network optimization.The increasing availability of large network data sets and the impact of networks on everyday life has set new standard to route computations,necessitating research for even faster and more accurate shortest path algorithms.A hierarchical graph model is developed based on an effective partition of graphs for decomposing the complex search problem.A new heuristic hierarchical routing algorithm is then proposed to significantly reduce the search space by pruning searches towards unpromising subgraph branches.Experimental results on New York City road network demonstrate the performance of the algorithm.
SONG Qing WANG Xiaofan
Department of Automation,Shanghai Jiao Tong University,and Key Laboratory of System Control and Information Processing,Ministry of Education of China,Shanghai 200240,P.R.China
国际会议
The 30th Chinese Control Conference(第三十届中国控制会议)
烟台
英文
1-5
2011-07-01（万方平台首次上网日期，不代表论文的发表时间）