An approximate algorithm for finding Steiner Forest.
- by Tadeusz A. Kadlubowski
Hello.
Consider a weighted graph G=(V,E,w). We are given a family of subsets of vertices V_i. Those sets of vertices are not necessarily disjoint.
A Steiner Forest is a forest that for each subset of vertices V_i connects all of the vertices in this subset with a tree.
Example: only one subset V_1 = V. In this case a Steiner forest is a spanning tree of the whole graph.
Enough theory. Finding such a forest with minimal weight is difficult (NP-complete). Do you know any quicker approximate algorithm to find such a forest with non-optimal weight?