On the complexity of time-dependent shortest paths
DOI10.1007/S00453-012-9714-7zbMATH Open1317.68069OpenAlexW3043093646MaRDI QIDQ476455FDOQ476455
Authors: Luca Foschini, Subhash Suri, John 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
Recommendations
approximation algorithmsparametric shortest pathpiecewise linear delay functionstime-dependent shortest path
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)
Cites Work
- Introduction to algorithms
- Title not available (Why is that?)
- Stochastic Shortest Paths Via Quasi-convex Maximization
- An Appraisal of Some Shortest-Path Algorithms
- Shortest paths in time-dependent FIFO networks
- Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Time-dependent route planning
- Title not available (Why is that?)
- An Analysis of Stochastic Shortest Path Problems
- The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
- Algorithms – ESA 2004
- Time depending shortest-path problems with applications to railway networks
- The weighted region problem
- Parametric Problems on Graphs of Bounded Tree-Width
- Title not available (Why is that?)
- Faster parametric shortest path and minimum‐balance algorithms
- Parametric shortest path algorithms with an application to cyclic staffing
- Bidirectional A ∗ Search for Time-Dependent Fast Paths
- Time-varying shortest path problems with constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (27)
- Computation of the optimal value function in time-dependent networks
- Energy-optimal routes for battery electric vehicles
- Improved approximation for time-dependent shortest paths
- The piecewise constant/linear solution for dynamic user equilibrium
- Perspectives on integer programming for time-dependent models
- An axiomatic approach to time-dependent shortest path oracles
- New complexity results for time-constrained dynamical optimal path problems
- On computing Pareto optimal paths in weighted time-dependent networks
- Scheduling activities with time-dependent durations and resource consumptions
- Engineering time-dependent many-to-many shortest paths computation
- Ant colony optimization algorithms with diversified search in the problem of optimization of airtravel itinerary
- Distributed shortest-path protocols for time-dependent networks
- Bi-directional search for robust routes in time-dependent bi-criteria road networks
- Distance oracles for time-dependent networks
- Vehicle routing with time-dependent travel times: theory, practice, and benchmarks
- Concerning the time bounds of existing shortest watchman route algorithms
- Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
- TSP race: minimizing completion time in time-sensitive applications
- On the complexity of time-dependent shortest paths
- Time-dependent shortest path problems with penalties and limits on waiting
- A polynomial algorithm for minimizing travel time in consistent time‐dependent networks with waits
- Shortest Journeys in Directed Temporal Graphs
- Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems
- Shortest paths in time-dependent FIFO networks
- Temporal matching on geometric graph data
- Shortest path with acceleration constraints: complexity and approximation algorithms
- NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times
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 Q476455)
