Speed-Up Techniques for Shortest-Path Computations

DOI10.1007/978-3-540-70918-3_3MaRDI QIDQ3590919zbMATH OpenOpenAlexFDO

Authors Dorothea Wagner, Thomas Willhalm

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70918-3_3

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Combining speed-up techniques for shortest-path computations
• Preprocessing speed-up techniques is hard
• Dijkstra's algorithm on-line
• Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
• Geometric speed-up techniques for finding shortest paths in large sparse graphs

Cited in

(24)

• A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
• A faster computation of the most vital edge of a shortest path
• Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments
• Disk-based shortest path discovery using distance index over large dynamic graphs
• scientific article; zbMATH DE number 434492 (Why is no real title available?)
• Bidirectional A  ∗  Search for Time-Dependent Fast Paths
• Combining speed-up techniques for shortest-path computations
• Preprocessing speed-up techniques is hard
• scientific article; zbMATH DE number 5734722 (Why is no real title available?)
• The Shortcut Problem – Complexity and Approximation
• Optimally fast shortest path algorithms for some classes of graphs
• scientific article; zbMATH DE number 1893565 (Why is no real title available?)
• OPTIMAL ROUTING BY LANDMARKS IN THE TIME-DEPENDENT NETWORKS
• Shortest-path queries in static networks
• SHARC: fast and robust unidirectional routing
• SHARC, fast and robust unidirectional routing
• Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
• LunarVis – Analytic Visualizations of Large Graphs
• Dijkstra's algorithm on-line
• Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks
• Experimental and Efficient Algorithms
• Experimental and Efficient Algorithms
• Geometric speed-up techniques for finding shortest paths in large sparse graphs
• Applying skeletons to speed up the Arc-Flags routing algorithm

This page was built for publication: Speed-Up Techniques for Shortest-Path Computations

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