search

franktakes / teexgraph

C++ library for large-scale network analysis and computation
GNU General Public License v3.0
23 stars 8 forks source link

Highway dimension? #12

Open r-barnes opened 3 years ago

r-barnes commented 3 years ago

Do you happen to have code for calculating highway dimension available anywhere?

franktakes commented 3 years ago

No, unfortunately not... But some of the ingredients for computing it are present in teexgraph, so it might be something that we can write an implementation for. Let's dicuss this!

r-barnes commented 3 years ago

I've just found "Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks", which looks as though it's able to bound the performance of contraction hierarchies without relying on the highway dimension. This might obviate my need to calculate it, but I'm not familiar enough with the literature to know if there are other quantities which still depend on it.

It's an interesting quantity because for almost a decade it was used to bound the performance of algorithms but we could neither calculate it empirically nor did we have good bounds on it (except for grids where it was Ω(√(N)).