NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times

DOI10.1016/j.ipl.2022.106287OpenAlexW4281620620MaRDI QIDQ2094362

Tim Zeitz

Publication date: 28 October 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2022.106287

zbMATH Keywords

NP-hardnesstheory of computationnon-FIFO time-dependent shortest paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Time-dependent routing problems: a review
• On the complexity of time-dependent shortest paths
• On strong NP-completeness of rational problems
• Bidirectional A* search on time-dependent road networks
• On a routing problem
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Time-Dependent Route Planning
• Minimum weight paths in time-dependent networks
• An Appraisal of Some Shortest-Path Algorithms
• Space-efficient, fast and exact routing in time-dependent road networks
• The NP-completeness column: An ongoing guide

This page was built for publication: NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times