[Routing] How to Establish Road Hierarchy

[Dennis Luxen]

Am 12.12.2012 um 02:00 schrieb David Piepgrass <dpiepgrass at mentoreng.com>:

>> Most probably Section 8 where the data set is explained if you are talking
>> about the paper "Efficient Routing in Road Networks with Turn Costs". There
>> is also a technical report somewhere that explores the impact of edge-
>> expansion by Lars Volker. Forgot the name of the TR.
> 
> That's the one. I don't see anything about the number of shortcuts in edge-based vs node-based graphs, in section 8 or elsewhere.

As I said, Section 8 is in the other paper. In the one you are refereeing to, there are query times. These more or less translate directly into settled nodes. The short answer is, according to Volker, the search space grows by about a factor of 2. Number of shortcuts should still be linear in the number of nodes.

One thing to keep an eye on during contraction is the average degree of the remaining graph. If it grows a lot then you get a spot to look at.

--Dennis