Paper Info
Title
Shortest Paths In Road Networks: From Practice To Theory And Back
Abstract
We illustrate the use of the scientific method in algorithmics by surveying recent developments in route planning on road networks. Several speed-up techniques proposed in the past decade are intuitive, elegant, and very efficient in practice, but lacked a theoretical explanation of their observed performance. By introducing a formal definition of road networks, recent theoretical work closed this gap. It also predicted that a previously untested algorithm should be even faster, which was confirmed by a subsequent implementation.
Year
DOI
Venue
2011
10.1524/itit.2011.0656
IT-INFORMATION TECHNOLOGY
Keywords
DocType
Volume
E.1 [Data Structures: Graphs and Networks], F.2.2 [Theory of Computation: Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems], G.2.2 [Mathematics of Computing: Discrete Mathematics: Graph Theory], G.2.3 [Mathematics of Computing: Discrete Mathematics: Applications], Algorithm Engineering
Journal
53
Issue
ISSN
Citations 
6
1611-2776
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Daniel Delling12049108.90
Andrew V. Goldberg25883676.30
Renato F. Werneck3174384.33