Geometric containers for efficient shortest-path computation

DOI10.1145/1064546.1103378MaRDI QIDQ5718630zbMATH OpenOpenAlexFDO

Authors Dorothea Wagner, Thomas Willhalm, Christos Zaroliagis

Publication date 16 January 2006

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1064546.1103378

zbMATH Keywords

Dijkstra's algorithmshortest path routine

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• Dynamic shortest paths containers
• Geometric speed-up techniques for finding shortest paths in large sparse graphs
• Algorithm engineering for route planning: an update
• An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags
• The shortest path problem on large-scale real-road networks

Cited in

(11)

• Engineering Route Planning Algorithms
• Bidirectional A  ∗  Search for Time-Dependent Fast Paths
• scientific article; zbMATH DE number 7121837 (Why is no real title available?)
• Regarding goal bounding and jump point search
• Shortest-path queries in static networks
• Engineering graph-based models for dynamic timetable information systems
• Efficient computation of geodesic shortest paths
• Dynamic shortest paths containers
• Bidirectional A^* search on time-dependent road networks
• Geometric speed-up techniques for finding shortest paths in large sparse graphs
• User-constrained multimodal route planning

Describes a project that uses

Uses Software

• AspectC++
• GraphML
• CGAL

This page was built for publication: Geometric containers for efficient shortest-path computation

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