Перевод названия: Approximate algorithm for searching shortest path in multiservice network with constrained resource
Тип публикации: статья из журнала
Год издания: 2019
Ключевые слова: ресурсоограниченный кратчайший путь, алгоритмы на графах, оптимальная маршрутизация, компьютерные и мультисервисные сети, resource constrained shortest path, Graph-based algorithm, Optimal routing, computer and multi-service networks
Аннотация: Предлагается приближённый алгоритм RevTree решения NP-трудной задачи RCSP (Resource Constrained Shortest Path). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V,E), когда для каждой дуги e £ E кроме основной весовой функции w(e) дополнительно задаются функции Ti(e), i = 1,...,k, численно отраПоказать полностьюжающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Задача RCSP возникает при проектировании и эксплуатации компьютерных и мультисервисных сетей. Показано, что алгоритм RevTree всегда находит допустимое решение задачи RCSP, если оно существует, за полиномиальное время, отклоняясь от оптимального решения на величину, зависящую от значений w(e) и ri(e), e £ E. In the paper, we consider 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 finite set of resource. The RCSP problem has various practical applications, including design and operation of multi-service network. Nowadays, multi-service networks grow at a rapid pace. Therefore, it is relevant to search for a new approximation algorithms that can solve the RCSP problem quickly. This paper reviews existing approximation algorithms for the RCSP problem. A polynomial time
Журнал: Прикладная дискретная математика. Приложение
Выпуск журнала: № 12
Номера страниц: 186-191
ISSN журнала: 2226308X
Место издания: Томск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет"