Bottleneck Steiner tree with bounded number of Steiner vertices Academic Article uri icon


  • Given a complete graph , where each vertex is labeled either terminal or Steiner, a distance function (i.e., a metric) , and a positive integer k, we study the problem of finding a Steiner tree T spanning all terminals and at most k Steiner vertices, such that the length of the longest edge is minimized. We first show that this problem is NP-hard and cannot be approximated within a factor of , for any , unless . Then, we present a polynomial-time 2-approximation algorithm for this problem.

publication date

  • January 1, 2015