Классы ориентированных градуированных графов с полиномиально разрешимой мощностной задачей Штейнера

Рассматривается задача Штейнера на ориентированных градуированных графах, где стоимость всех дуг единична. Дается описание двух классов графов, в которых рассматриваемая задача разрешима за полиномиальное время. Графы из этих классов получаются из деревьев добавлением вершин и ребер, образующих пути длины 2, с сохранением градуированности и достижимости. Предлагаются алгоритмы решения мощностной задачи Штейнера на графах из описанных классов и алгоритмы распознавания принадлежности произвольного ориентированного градуированного графа этим классам. Сложность этих алгоритмов есть $O(n^{4})$, где $n$ — число вершин в графе.