Name
Abstract | ||
|---|---|---|
Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a unified explanation for several seemingly different algorithms. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.5555/1873601.1873665 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
provably efficient algorithm,different algorithm,low highway dimension,past decade,answer query,computing driving direction,experimental evidence,shortest path heuristics,continental scale network,low storage overhead,highway dimension,shortest path | Discrete mathematics,Combinatorics,Shortest path problem,Computer science,Algorithm,Contraction hierarchies,Heuristics,Mathematical proof,K shortest path routing | Conference |
Volume | ISBN | Citations |
135 | 978-0-89871-698-6 | 66 |
PageRank | References | Authors |
2.88 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ittai Abraham | 1 | 1483 | 89.62 |
| Amos Fiat | 2 | 3977 | 685.20 |
| Andrew V. Goldberg | 3 | 5883 | 676.30 |
| Renato F. Werneck | 4 | 1743 | 84.33 |