@article {
author = {Shirdel, Gholam Hassan and Rezapour, Hassan},
title = {Approximation Solutions for Time-Varying Shortest Path Problem},
journal = {Communications in Combinatorics and Optimization},
volume = {2},
number = {2},
pages = {139-147},
year = {2017},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2017.25850.1047},
abstract = {Time-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 $O\big(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 $O\big(\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\}$.},
keywords = {Time-Varying Optimization,Approximation solutions,Shortest Path Problem},
url = {http://comb-opt.azaruniv.ac.ir/article_13645.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13645_0d39e0bfe8ae0a66991a25e4ac1ac564.pdf}
}