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
article (PDF)
BibTeX