Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях
Аннотация
Дата поступления статьи: 28.01.2015Рассмотрена задача маршрутизации в информационной сети, в которой имеются дуги, не влияющие на качество сигнала – нейтральные, и снижающие качество сигнала – регрессивные, а также вершины, в которых качество сигнала улучшается – активные. Задача сводится к нахождению кратчайшего пути на множестве путей, удовлетворяющих дополнительному ограничению- любой отрезок пути заключенный между двумя соседними активными вершинами содержит не более заданного количества регрессивных дуг. Построена развёртка , позволяющая находить решение исходной задачи с ограничениями как решение соответствующей задачи без ограничений на развертке.
Ключевые слова: граф, путь, достижимость, развертка графа, маршрутизация
05.13.01 - Системный анализ, управление и обработка информации (по отраслям)
05.13.18 - Математическое моделирование, численные методы и комплексы программ