2010/12/07 by A. Karim Abu-Affash, Abu-Affash, A. Karim
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1012.1502
arxiv created 2010/12/07 · arxiv updated 2010/12/08
Given two sets of points in the plane, P of n terminals and S of m Steiner points, a Steiner tree of P is a tree spanning all points of P and some (or none or all) points of S. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, P and S, and a positive integer k ≤ m, find a bottleneck Steiner tree of P with at most k Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor √(2), unless P=NP. Then, we present a polynomial-time approximation algorithm with performance ratio 2.