An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time
0(¦V¦ ¦E¦ + ¦S¦
4), where
V is the vertex set,
E is the edge set of the graph, and
S is the given subset of vertices.
Keywords Steiner tree - Approximation algorithm
Communicated by Christos H. Papadimitriou.