Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that | W | = k , for a fixed positive integer k. The enumeration is performed within O ( n ) delay, where n = | V ( G ) | consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset W ⊆ V ( G ) can be computed in polynomial time, provided that the size of W is bounded by a constant.