Топологические методы решения задачи штейнера на графе

Рассматриваются методы построения алгоритмов для задачи Штейнера и ряда ее обобщений на больших графах с относительно малым числом терминальных вершин. Данные методы используют двухуровневую схему решения: на верхнем уровне осуществляется синтез топологии сети (т.е. дерева, определяющего смежность терминальных вершин и точек ветвления), а на нижнем уровне определяется оптимальное размещение точек ветвления сети с топологией, передаваемой с верхнего уровня.

Статья представлена к публикации членом редколлегии: А. И. Кибзун