Geodesic
New complexity results for time-constrained dynamical optimal path problems
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 123-147.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00201
Keywords: time-dependent networks, constrained optimization, pruning, complexity 
@article{JGAA_2010_14_2_a0,
     author = {Sebastian Kluge and Martin Brokate and Konrad Reif},
     title = {New complexity results for time-constrained dynamical optimal path problems},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {123--147},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00201},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00201/}
}
TY  - JOUR
AU  - Sebastian Kluge
AU  - Martin Brokate
AU  - Konrad Reif
TI  - New complexity results for time-constrained dynamical optimal path problems
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 123
EP  - 147
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00201/
DO  - 10.7155/jgaa.00201
LA  - en
ID  - JGAA_2010_14_2_a0
ER  - 
%0 Journal Article
%A Sebastian Kluge
%A Martin Brokate
%A Konrad Reif
%T New complexity results for time-constrained dynamical optimal path problems
%J Journal of Graph Algorithms and Applications
%D 2010
%P 123-147
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00201/
%R 10.7155/jgaa.00201
%G en
%F JGAA_2010_14_2_a0
Sebastian Kluge; Martin Brokate; Konrad Reif. New complexity results for time-constrained dynamical optimal path problems. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 123-147. doi : 10.7155/jgaa.00201. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00201/

Cité par Sources :