Reach for A^*: shortest path algorithms with preprocessing

MaRDI QIDQ3574264zbMATH OpenFDO

Authors Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck

Publication date 9 July 2010

zbMATH Keywords

shortcutslandmark-based \(A^*\) searchsource-to-destination queries

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• Reach for \(A^\ast\): efficient point-to-point shortest path algorithms
• Point-to-Point Shortest Path Algorithms with Preprocessing
• Engineering Highway Hierarchies
• Engineering highway hierarchies
• Goal-directed shortest-path queries using precomputed cluster distances

Cited in

(18)

• Goal-directed shortest-path queries using precomputed cluster distances
• Dynamic graph generation for the shortest path problem in time expanded networks
• Core routing on dynamic time-dependent road networks
• Preprocessing speed-up techniques is hard
• VC-dimension and shortest path algorithms
• Reach for \(A^\ast\): efficient point-to-point shortest path algorithms
• Point-to-Point Shortest Path Algorithms with Preprocessing
• PReaCH: a fast lightweight reachability index using pruning and contraction hierarchies
• Candidate sets for alternative routes in road networks
• Shortest-path queries in static networks
• The shortest-path problem. Analysis and comparison of methods
• Precomputation techniques for the stochastic on-time arrival problem
• Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
• Computing the shortest path: \(A^\ast\) search meets graph theory
• GRASP. Extending graph separators for the single-source shortest-path problem
• The compressed differential heuristic
• An efficient lower-bounding approach to point-to-point shortest path problem
• Optimal forks: preprocessing single-source shortest path instances with interval data

This page was built for publication: Reach for \(A^*\): shortest path algorithms with preprocessing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3574264)