Classes of oriented graded graphs with polynomially solvable cardinality Steiner problem

V. A. Shcherbakova

Diskretnaya Matematika, Tome 9 (1997) no. 4, pp. 73-85.

Résumé

In this paper the cardinality Steiner problem on directed graded graphs is considered, where the costs of all edges are equal to one. We describe two graph classes where the considered problem is solvable in a polynomial time. The graphs of these classes are generated from trees by adding vertices and edges forming paths of length 2. We give algorithms to solve the cardinality Steiner problem on graphs from the described classes and algorithms to recognize whether an arbitrary directed graded graph belongs to the corresponding class. The complexity of these algorithms is $O(n^4)$, where $n$ is the number of vertices of the graph.