Тип публикации: статья из журнала
Год издания: 2019
Идентификатор DOI: 10.17516/1997-1397-2019-12-5-621-627
Ключевые слова: Combinatorial optimization, Efficient approximation algorithm, Graph-based algorithm, Resource constrained shortest path
Аннотация: The paper we considers the Resource Constrained Shortest Path problem (RCSP). This problem is NP-hard extension of a well-known shortest path problem in the directed graph G = (V, E). In the RCSP problem each arc e from E has a cost w(e) and additional weight functions ri (e), i = 1, …, k, which specifying its requirements from a fПоказать полностьюinite set of resource. A polynomial time ϵ-approximation algorithm RevTree based on node labeling method is presented in the paper. The main advantage of the RevTree algorithm over existing ones is its ability to produce ϵ approximation of the RCSP problem in O(|V|2) time. The present paper provides a proof of complexity and aproximation of RevTree algorithm. © Siberian Federal University.
Журнал: Journal of Siberian Federal University - Mathematics and Physics
Выпуск журнала: Vol. 12, Is. 5
Номера страниц: 621-627
ISSN журнала: 19971397
Издатель: Siberian Federal University