On the complexity of time-dependent shortest paths

MaRDI QIDQ5365046zbMATH OpenFDO

Authors Luca Foschini, John Hershberger, Subhash Suri

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133063

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• On the complexity of time-dependent shortest paths
• Improved approximation for time-dependent shortest paths
• Shortest paths in time-dependent FIFO networks
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Time-varying shortest path problems with constraints

Cited in

(13)

• Shortest path with acceleration constraints: complexity and approximation algorithms
• NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times
• Shortest paths in time-dependent FIFO networks
• Engineering time-dependent many-to-many shortest paths computation
• Improved approximation for time-dependent shortest paths
• TSP race: minimizing completion time in time-sensitive applications
• New complexity results for time-constrained dynamical optimal path problems
• On the complexity of time-dependent shortest paths
• Concerning the time bounds of existing shortest watchman route algorithms
• Distributed shortest-path protocols for time-dependent networks
• Shortest Journeys in Directed Temporal Graphs
• A time-dependent subgraph-capacity model for multiple shortest paths and application to \(\text{CO}_2\)/contrail-safe aircraft trajectories
• A robust method for fast exploration of environments with moving obstacles

This page was built for publication: On the complexity of time-dependent shortest paths

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