Approximating the selected-internal Steiner tree

被引：10

作者：

Hsieh, Sun-Yuan ^{[1
]}

Yang, Shih-Cheng ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan

来源：

THEORETICAL COMPUTER SCIENCE | 2007年 / 381卷 / 1-3期

关键词：

design and analysis of algorithms; approximation algorithms; steiner tree; the selected-internal steiner tree problem; MAX SNP-hard;

D O I：

10.1016/j.tcs.2007.05.035

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G = (V, E) with a cost function c : E -> R+ and two subsets R and R' satisfying R' subset of R subset of V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R' cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a 2 rho-approximation algorithm for the problem, where p is the best-known approximation ratio for the Steiner tree problem. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：288 / 291

页数：4

共 14 条

[1] Proof verification and the hardness of approximation problems [J].