Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00201 New complexity results for time-constrained dynamical optimal path problems Sebastian Kluge , Martin Brokate , and Konrad Reif 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.
|
Published: January 2010. Final: October 2009. Revised: October 2009. Submitted: June 2009. Reviewed: September 2009. Accepted: October 2009. Communicated by Dorothea Wagner |
| Journal of Graph Algorithms and Applications |