The internal Steiner tree problem: Hardness and approximations

Chao Wen Huang, Chia Wei Lee, Huang Ming Gao, Sun Yuan Hsieh

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Given a graph G=(V,E) with a cost function c:E→ℝ+ and a vertex subset R⊂V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost ∑(u,v)∈E(T)c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2ρ+1)-approximation algorithm for solving the problem on complete graphs, where ρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρ is ln4+ε<1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 9/7-approximation algorithm for the problem.

Original languageEnglish
Pages (from-to)27-43
Number of pages17
JournalJournal of Complexity
Volume29
Issue number1
DOIs
Publication statusPublished - 2013 Feb

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics(all)
  • Control and Optimization
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The internal Steiner tree problem: Hardness and approximations'. Together they form a unique fingerprint.

  • Cite this