A hub-based labeling algorithm for shortest paths in road networks
Experimental Algorithms: 10th International Symposium, SEA 2011, Kolimpari�…, 2011•Springer
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.
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.
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.
Springer
Showing the best result for this search. See all results