The Shortcut Problem – Complexity and Approximation

DOI10.1007/978-3-540-95891-8_13MaRDI QIDQ3599067zbMATH OpenOpenAlexFDO

Authors Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling, Dorothea Wagner

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_13

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• The shortcut problem - complexity and algorithms
• Computing optimal shortcuts for networks
• Finding the best shortcut in a geometric network
• The shortest path problem on large-scale real-road networks
• Speed-Up Techniques for Shortest-Path Computations

Cites work

• Dijkstra's algorithm on-line
• Dynamic multi-level overlay graphs for shortest paths
• Engineering Highway Hierarchies
• Engineering multilevel overlay graphs for shortest-path queries
• Experimental algorithms. 6th international workshop, WEA 2007, Rome, Italy, June 6--8, 2007. Proceedings.
• Experimental algorithms. 7th international workshop, WEA 2008 Provincetown, MA, USA, May 30--June 1, 2008. Proceedings
• scientific article; zbMATH DE number 1926659 (Why is no real title available?)
• On the Distribution of the Number of Successes in Independent Trials
• SHARC, fast and robust unidirectional routing
• Speed-Up Techniques for Shortest-Path Computations

Cited in

(5)

• Computing optimal shortcuts for networks
• The shortcut problem - complexity and algorithms
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Shortest-path queries in static networks
• Exact distance oracles for planar graphs

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: The Shortcut Problem – Complexity and Approximation

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