Partitioning graphs to speedup Dijkstra's algorithm

DOI10.1145/1187436.1216585MaRDI QIDQ3507777zbMATH OpenOpenAlexFDO

Authors Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, Thomas Willhalm

Publication date 20 June 2008

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

Full work available at URL https://depositonce.tu-berlin.de/handle/11303/15567

zbMATH Keywords

arc-flag method

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 5734722
• Experimental and Efficient Algorithms
• Engineering Highway Hierarchies
• On the complexity of partitioning graphs for arc-flags

Cited in

(16)

• A note on the partitioning shortest path algorithm
• On the complexity of partitioning graphs for arc-flags
• On the complexity of partitioning graphs for arc-flags
• Combining speed-up techniques for shortest-path computations
• High-performance multi-level routing
• Engineering Route Planning Algorithms
• Map partitioning for accelerated routing: measuring relation between tiled and routing partitions
• Shortest-path queries in static networks
• Time-dependent SHARC-routing
• Experimental and Efficient Algorithms
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• ILP-Based Local Search for Graph Partitioning
• A novel pseudo‐polynomial approach for shortest path problems
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• Applying skeletons to speed up the Arc-Flags routing algorithm
• Connected partitions via connected dominating sets

This page was built for publication: Partitioning graphs to speedup Dijkstra's algorithm

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