An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem

Details An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem

2010-12-07

arxiv.org/abs/1012.1502v1

Computer Science

Computational Geometry

Scientific paper

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 \le 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 $\sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.

Affiliated with

Also associated with

No associations

Rating

An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480808