TY  - SER
AU  - Солдатенко,Александр Александрович
TI  - Приближенный алгоритм поиска оптимального маршрута в сети с ограничением
KW  - ресурсоограниченный кратчайший путь
KW  - алгоритмы на графах
KW  - оптимальная маршрутизация
KW  - компьютерные сети
KW  - мультисервисные сети
KW  - статьи в журналах
N1  - Библиогр.: 10 назв
N2  - Предлагается приближённый алгоритм RevTree решения NP-трудной задачи RCSP (Resource Constrained Shortest Path). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V, E), когда для каждой дуги e G E кроме основной весовой функции w(e) дополнительно задаются функции ri(e), i = 1,. . . ,k, численно отражающие потребности в ресурсах, которые необходимы для = передвижения по этой дуге. Задача RCSP возникает при проектировании и эксплуатации компьютерных и мультисервисных сетей. Показано, что алгоритм RevTree всегда находит допустимое решение задачи RCSP, если оно существует, за полиномиальное время, отклоняясь от оптимального решения на величину, зависящую от значений w(e) и ri(e), e G E
UR  - http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000724655
ER  -