Мощностная задача Штейнера на ориентированном градуированном графе

Abstract

Дается обзор результатов автора, посвященных задаче нахождения минимального по числу вершин поддерева, содержащего заданное множество помеченных вершин в заданном ориентированном градуированном графе. Показано, что такая задача NP-трудна. Обсуждаются различные точные и приближенные алгоритмы ее решения. Описаны два класса графов, в которых (при подходящем расположении помеченных вершин) исследуемая задача полиномиально разрешима.

We survey the author’s result devoted to the problem of determining the minimal (in the vertex number) subtree containing a prescribed set of marked vertices of a directed graded graph. The problem is shown to be NP-hard. We discuss several exact and approximate algorithms for its solution and describe two classes of graphs in which the problem admits a solution in polynomial time (provided a suitable disposition of marked vertices).