A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points

We give a tight analysis of the MST heuristic recently introduced by G.-H. Lin and G. Xue for approximating the Steiner tree with minimum number of St einer points and bounded edge-lengths. The approximation factor of the heur istic is shown to be one less than the MST number of the underlying space, defined as the maximum possible degree of a minimum-degree MST spanning poi nts from the space. In particular, on instances drawn from the rectilinear (respectively Euclidean) plane, the MST heuristic is shown to have tight ap proximation factors of 3, respectively 4. (C) 2000 Elsevier Science B.V. Al l rights reserved.