约束Steiner最小树问题的近似解

An Approximation Solution of the Constrained Steiner Minimum Tree Problem

本文首先给出约束Steiner最小树问题的一个近似解。然后讨论了当n=2或3时近似解的性能比，其中n=2时，文中所给的界为紧的。

In this aticle, we propose an approximation solution to the constrained Steiner minimum tree problem, Then we give the Performance ratio of this approxbotion solution for n = 2 or 3.Moreover, this ratio is tight when n = 2.