New complexity results for time-constrained dynamical optimal path problems - Kluge, Sebastian; Brokate, Martin; Reif, Konrad (Journal of Graph Algorithms and Applications, 2010)
In this paper, we consider time-dependent networks, and the task of computing cost-optimal paths, which are constrainedto stay close to fastest paths. We derive pruning criteria, which significantly improve both the number of vertex-timepairs expanded during search and the memory required to ensure the correctness of any solution algorithm. We then provenew complexity results, which imply that the problem of computing constrained cost-optimal paths in a discrete-time settingis polynomially solvable for several graph and constraint classes. <!---->