The shortcut problem - complexity and algorithms

DOI10.7155/JGAA.00270MaRDI QIDQ3143749zbMATH OpenOpenAlexFDO

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

Publication date 4 December 2012

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00270

zbMATH Keywords

route planninggraph-augmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• The Shortcut Problem – Complexity and Approximation
• Computing optimal shortcuts for networks
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Finding the best shortcut in a geometric network
• Shortcutting directed and undirected networks with a degree constraint

Cited in

(5)

• Customizable contraction hierarchies
• Improving the betweenness centrality of a node by adding links
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Shortcutting directed and undirected networks with a degree constraint
• The Shortcut Problem – Complexity and Approximation

This page was built for publication: The shortcut problem - complexity and algorithms

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