Алгоритм $k$-кластерной оптимизации для задачи Штейнера на ориентированных графах

Задача Штейнера на ориентированных графах – наиболее общая в семействе задач Штейнера. Имея граф $G(M,N)$, $b\in M$, $E\subset M$, необходимо найти наименьший подграф $G$, содержащий пути от $b$ до всех вершин из $E$. В статье представлен эвристический алгоритм, основанный на разбиении графа на подграфы и решении задачи Штейнера на них точным методом. Доказывается теорема о вычислительной сложности метода и приводится сравнение на экспериментальных данных с известными приближенными методами. Библиогр. 8 назв.