Задача Штейнера для ацикдического графа

Журнал: 
Страница: 
18
УДК: 
519.6
В статье рассматривается задача Штейнера для ациклического графа. Исследование и решение задачи проводится с использованием алгебраического подхода. Введены операции над множеством простых цепочек, рассмотрены свойства этих операций. Определены понятия полноты, базиса, канонического базиса для множества простых цепочек. Предложен простой алгоритм решения задачи, использующий заранее вычисленные базисные цепочки. Показана полиномиальная разрешимость задачи.