next up previous
Next: Branch and Bound Up: More about trees Previous: Minimum Spanning Trees

Steiner Trees

In order to make the paths shorter between the cities,people used crossroads, extra points added to the road systems that make the paths shorter, this is what Steiner trees do.

Unfortunately this method has the same problem as the ML method, it is NP complete. In real data sitiuations we will have to rely on heuristics producing not necessarily optimal solution.

These are based on clever ways of going through the possible trees so as not to have to look at all off them completely.

Prof. Susan Holmes
Tue Mar 24 14:40:11 EST 1998