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 time0(¦V¦ ¦E¦ + ¦S¦4), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.
No takes yet. Share an insight, caveat, or question.
Alex Zelikovsky (1993) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: