The k-steiner ratio in graphs. - Borchers, Al
A Steiner minimum tree (SMT) is the shortest-length tree in a metric space interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-Steiner ratio is the infimum of the ratios SMT/kSMT over all finite sets of regular points in all possible metric spaces, where the distances are given by a complete graph. Previously, only p2 and p3 where known exactly in graphs, and some bounds were known for other values of k. In this paper, we determine pk exactly for all k. From this we prove a better approximation ratio for the Steiner tree problem in graphs
Keywords: Steiner trees; Steiner ratio; Approximation algorithms; Graph algorithms; Graph theory