Speed-Up Techniques for Shortest-Path Computations

DOI10.1007/978-3-540-70918-3_3zbMATH Open1186.68594OpenAlexW2110452945MaRDI QIDQ3590919FDOQ3590919

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

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

Mathematics Subject Classification ID

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

Cited In (24)

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