In this paper, we consider the problem of 1-line minimum lambda-Steiner tree problem, denoted as the 1L-M(lambda)StT problem. Given a set X = {r(1), r(2),..., r(n)} of n points in the lambda-plane and a straight line ...
详细信息
ISBN:
(纸本)9789819614899;9789819614905
In this paper, we consider the problem of 1-line minimum lambda-Steiner tree problem, denoted as the 1L-M(lambda)StT problem. Given a set X = {r(1), r(2),..., r(n)} of n points in the lambda-plane and a straight line l in R-2, we need to construct a Steiner tree T-l connecting the n points in X and the straight line l. The objective is to minimize the total cost of such a Steiner tree T-l, i.e.,min{Sigma(epsilon is an element of Tl) w(e) | T-l is the mentioned Steiner tree}, and if an edge e = uv is an element of T-l has both endpoints u and v lying on the line l, the weight is defined as w(e) = 0;Otherwise, it is defined as the distance of the two endpoints u and v in the lambda-plane. In particular, if all Steiner points in T-l are constrained to lie on the line l, the problem is denoted as the 1-line minimum lambda-spanningtree (1L-M lambda ST) problem. We present two main results. (1) By using the strategies of the sweep-line algorithm, we can design an exact algorithm in time O(lambda n log n) to solve the 1L-M lambda ST problem;(2) Using some properties of lambda-plane, we showed that our algorithm is a rho(lambda)-approximation algorithm for the 1L-M(lambda)StT problem, where rho(lambda) is inverse of the Steiner ratio in the lambda-plane.
暂无评论