A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree |
| |
Authors: | Xianyue Li Feng Zou Yaochun Huang Donghyun Kim Weili Wu |
| |
Affiliation: | 1. School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, 730000, P.R. China 2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA
|
| |
Abstract: | The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted
complete graph G=(V,E) with weight function c, and two subsets R
′
⊊
R⊆V with |R−R
′|≥2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R
′. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|