An 11/6-approximation algorithm for the network steiner problem 论文
1993Algorithmica引用 337
VLSI and FPGA Design TechniquesComplexity and Algorithms in GraphsOptimization and Packing Problems
摘要
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.