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