Abstract | ||
---|---|---|
Abraham et al. [SODA 2010] have recently presented a theoretical analysis of several practical point-to-point shortest path algorithms based on modeling road networks as graphs with low highway dimension. They also analyze a labeling algorithm. While no practical implementation of this algorithm existed, it has the best time bounds. This paper describes an implementation of the labeling algorithm that is faster than any existing method on continental road networks. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-20662-7_20 | SEA |
Keywords | Field | DocType |
low highway dimension,road network,existing method,practical implementation,continental road network,practical point-to-point shortest path,best time bound,theoretical analysis,shortest path,point to point,shortest path algorithm | Shortest path problem,Computer science,Constrained Shortest Path First,Algorithm,Yen's algorithm,Floyd–Warshall algorithm,Suurballe's algorithm,Shortest Path Faster Algorithm,Euclidean shortest path,K shortest path routing | Conference |
Volume | ISSN | Citations |
6630 | 0302-9743 | 99 |
PageRank | References | Authors |
3.40 | 25 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ittai Abraham | 1 | 1483 | 89.62 |
Daniel Delling | 2 | 2049 | 108.90 |
Andrew V. Goldberg | 3 | 5883 | 676.30 |
Renato F. Werneck | 4 | 1743 | 84.33 |