Задача Штейнера на ориентированных графах – наиболее общая в семействе задач Штейнера. Известно, что она является NP-полной. Существует алгоритм для точного решения задачи, основанный на динамическом программировании, пригодный для задач маленького размера. В нашей статье приводятся специальные типы задач, на которых с помощью модификации названного метода точное решение может быть получено за полиномиальное время. Кроме того, представлен метод, предназначенный для приближенного решения произвольных задач Штейнера на ориентированных графах.

Steiner tree problem on oriented graphs is the most general in the family of Steiner tree problems. It is known to be NP-complete. There exists an algorithm to find an exact solution, based on dynamic programming, but applicable only for problems of modest size. Here special types of problems are presented, for which this algorithm is modified to find exact solution at polynomial time. Also approximate method, based on this algorithm for solving arbitrary problems is produced.