An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

Chia Chen Wei, Sun Yuan Hsieh, Chia Wei Lee, Sheng Lung Peng

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Given a complete graph G=(V,E) with a metric cost function c:E→R+ and two vertex subsets R⊂V and R′⊆R, a partial-terminal Steiner tree is a Steiner tree which contains all the vertices in R such that all the vertices in R′ are leaves. The partial-terminal Steiner tree problem (PTSTP) is to find a partial-terminal Steiner tree with the minimum cost. The problem has been shown to be NP-hard and MAX SNP-hard, even when the edge costs are restricted in {1,2}, namely, the (1,2)-partial-terminal Steiner tree problem (PTSTP(1,2)). In this paper, we consider PTSTP(1,2). The previous best-known approximation ratio of PTSTP(1,2) was at most 2514. In this paper, we propose a polynomial-time approximation algorithm that improves the approximation ratio from 2514 to 53.

Original languageEnglish
Pages (from-to)62-71
Number of pages10
JournalJournal of Discrete Algorithms
Volume35
DOIs
Publication statusPublished - 2015 Nov

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2'. Together they form a unique fingerprint.

Cite this