Approximations for a bottleneck steiner tree problem

L. Wang, D. Z. Du

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

In the design of wireless communication networks, due to a budget limit, suppose we could put totally n + k stations in the plane. However, n of them must be located at given points. Of course, one would like to have the distance between stations as small as possible. The problem is how to choose locations for other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP ≠ P, no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than √2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane.

Original languageEnglish (US)
Pages (from-to)554-561
Number of pages8
JournalAlgorithmica (New York)
Volume32
Issue number4
DOIs
StatePublished - Jan 1 2002

Keywords

  • Steiner tree
  • Wireless communication

Fingerprint Dive into the research topics of 'Approximations for a bottleneck steiner tree problem'. Together they form a unique fingerprint.

Cite this