تعداد نشریات | 7 |
تعداد شمارهها | 52 |
تعداد مقالات | 348 |
تعداد مشاهده مقاله | 413,963 |
تعداد دریافت فایل اصل مقاله | 288,339 |
Approximation Solutions for Time-Varying Shortest Path Problem | ||
Communications in Combinatorics and Optimization | ||
مقاله 5، دوره 2، شماره 2، پاییز 2017، صفحه 139-147 اصل مقاله (440 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2017.25850.1047 | ||
نویسندگان | ||
Gholam Hassan Shirdel ![]() | ||
1University of Qom | ||
2Unuversity of Qom | ||
چکیده | ||
Abstract. Time-varying network optimization problems have tradition- ally been solved by specialized algorithms. These algorithms have NP- complement time complexity. This paper considers the time-varying short- est path problem, in which can be optimally solved in O(T(m + n)) time, where T is a given integer. For this problem with arbitrary waiting times, we propose an approximation algorithm, which can solve the problem with O(T(m+n)/ k ) time complexity such that evaluates only a subset of the values for t = {0, 1, . . . , T}. | ||
کلیدواژه ها | ||
Time-Varying Optimization؛ Approximation solutions؛ Shortest Path Problem | ||
آمار تعداد مشاهده مقاله: 778 تعداد دریافت فایل اصل مقاله: 559 |
||