On the complexity of time-dependent shortest paths

DOI10.1007/S00453-012-9714-7zbMath1317.68069OpenAlexW3043093646MaRDI QIDQ476455

Luca Foschini, Subhash Suri, J. E. Hershberger

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9714-7

zbMATH Keywords

approximation algorithmsparametric shortest pathpiecewise linear delay functionstime-dependent shortest path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Distance oracles for time-dependent networks ⋮ Scheduling activities with time-dependent durations and resource consumptions ⋮ On computing Pareto optimal paths in weighted time-dependent networks ⋮ Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting ⋮ Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems ⋮ Ant colony optimization algorithms with diversified search in the problem of optimization of airtravel itinerary ⋮ Unnamed Item ⋮ A polynomial algorithm for minimizing travel time in consistent time‐dependent networks with waits ⋮ The piecewise constant/linear solution for dynamic user equilibrium ⋮ Temporal matching on geometric graph data ⋮ Perspectives on integer programming for time-dependent models ⋮ Energy-optimal routes for battery electric vehicles ⋮ Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles ⋮ NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times ⋮ An axiomatic approach to time-dependent shortest path oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parametric shortest path algorithms with an application to cyclic staffing
• Time depending shortest-path problems with applications to railway networks
• Shortest paths in time-dependent FIFO networks
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Bidirectional A  ∗  Search for Time-Dependent Fast Paths
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Time-Dependent Route Planning
• An Analysis of Stochastic Shortest Path Problems
• Parametric Problems on Graphs of Bounded Tree-Width
• The weighted region problem
• Time-varying shortest path problems with constraints
• The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Algorithms – ESA 2004
• An Appraisal of Some Shortest-Path Algorithms
• Faster parametric shortest path and minimum‐balance algorithms

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