Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Approximation Solutions for Time-Varying Shortest Path Problem1391471364510.22049/cco.2017.25850.1047ENGholam HassanShirdelUniversity of Qom0000000327594606HassanRezapourUnuversity of QomJournal Article20170103Time-varying network optimization problem, which is NP-complete in the ordinary sense, are traditionally solved by specialized algorithms. This paper considers the time-varying shortest path problem, which can be optimally solved in $Obig(T(m+n)big)$ time, where $T$ is a given integer. For this problem with arbitrary waiting times, we propose an approximate algorithm, which can find an acceptable solution of the problem with $Obig(frac{T(m+n)}{k}big)$ time complexity such that it evaluates only a subset of the values for $t in {0, 1,ldots,T}$.http://comb-opt.azaruniv.ac.ir/article_13645_0d39e0bfe8ae0a66991a25e4ac1ac564.pdf