Heuristic Contraction Hierarchies with Approximation Guarantee

Details Heuristic Contraction Hierarchies with Approximation Guarantee Heuristic Contraction Hierarchies with Approximation Guarantee

2010-02-04

arxiv.org/abs/1002.1021v1

Computer Science

Data Structures and Algorithms

7 pages, technical report

Scientific paper

We present a new heuristic point-to-point routing algorithm based on contraction hierarchies (CH). Given an epsilon >= 0, we can prove that the length of the path computed by our algorithm is at most (1+epsilon) times the length of the optimal (shortest) path. CH is based on node contraction: removing nodes from a network and adding shortcut edges to preserve shortest path distances. Our algorithm tries to avoid shortcuts even when a replacement path is epsilon times longer.

Affiliated with

Also associated with

No associations

Rating

Heuristic Contraction Hierarchies with Approximation Guarantee does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Heuristic Contraction Hierarchies with Approximation Guarantee, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heuristic Contraction Hierarchies with Approximation Guarantee will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-155320