Эвристический подход к проблеме минимального расширениякоммуникационной сети и его оценка, основанная на использовании специального класса графов

В статье представлен эвристический подход к проблеме изменения топологии сети путём минимального расширения ориентированного графа G' с помощью добавления рёбер из суперграфа G графа G' таким образом, что сумма стоимостей новых рёбер минимальна и общая задержка между двумя выделенными узлами s и t удовлетворяет заранее определённым ограничениям. Для решения этой проблемы авторами разработан алгоритм генетического типа. Более того, проведена оценка эвристического подхода с использованием специального класса ориентированных графов, и показано, что решение проблемы минимального расширения коммуникационной сети с ограничениями на задержку принадлежит к классу NP-полных вычислительных задач.

networks, Genetic Algorithm, NP-hard, delay and cost constraints