Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00201
New complexity results for time-constrained dynamical optimal path problems
Vol. 14, no. 2, pp. 123-147, 2010. Regular paper.
Abstract In this paper, we consider time-dependent networks, and the task of computing cost-optimal paths, which are constrained
to stay close to fastest paths. We derive pruning criteria, which significantly improve both the number of vertex-time
pairs expanded during search and the memory required to ensure the correctness of any solution algorithm. We then prove
new complexity results, which imply that the problem of computing constrained cost-optimal paths in a discrete-time setting
is polynomially solvable for several graph and constraint classes.
|
Submitted: June 2009.
Reviewed: September 2009.
Revised: October 2009.
Accepted: October 2009.
Final: October 2009.
Published: January 2010.
Communicated by
Dorothea Wagner
|
Journal Supporters
|