Exact Algorithms
Hans Jürgen Prömel, Angelika Steger · Advanced lectures in mathematics · 2002
The Steiner Problem in Networks deals with finite objects only. So, in principle, the problem can easily be solved: just enumerate all subsets of the edges, check whether they form a Steiner tree which span the given terminal set, and keep the smallest one. Although such an approach leads to a finite algorithm, it is certainly not a very efficient one. Its complexity is exponential in the number of edges of the network. On the other hand, as we have seen in Chapter 3, so far there is no polynomial time algorithm known for the Steiner Problem in Graphs and, hence, in particular none for the Steiner Problem in Networks .