The relationship among some variables of Steiner tree problem

Author

Zhao, Chenxia ; Li, Xianyue

Author_Institution

Sch. of Math. & Stat., Lanzhou Univ., Lanzhou, China

fYear

2012

fDate

3-5 June 2012

Firstpage

155

Lastpage

157

Abstract

Given a weighted complete graph G = (V, E; w) and a subset R⊆V, the Steiner tree problem (STP) is to find a minimum sub-tree of G interconnecting R. In this paper, we consider the relationship among the following 4 variables of STP: terminal Steiner tree problem (TSTP), partial-terminal Steiner tree problem (PTSTP), internal Steiner tree problem (ISTP) and selected-internal Steiner tree problem (SISTP). Firstly, we show that if SISTP has an approximation problem with approximation ratio, then ISTP also has an approximation algorithm with the same ratio. Then, we prove that the same result holds between PTSTP and TSTP.

Keywords

approximation theory; computational complexity; trees (mathematics); ISTP; NP-complete combinatorial optimization problem; PTSTP; SISTP; TSTP; approximation problem; approximation ratio; internal Steiner tree problem; minimum subtree; partial-terminal Steiner tree problem; selected-internal Steiner tree problem; terminal Steiner tree problem; weighted complete graph; Approximation algorithms; Approximation methods; Computer science; Educational institutions; Robots; Steiner trees; Steiner tree; approximation algorithm; internal Steiner tree; partial-terminal Steiner tree; selected-internal Steiner tree; terminal Steiner tree;

fLanguage

English

Publisher

ieee

Conference_Titel

Robotics and Applications (ISRA), 2012 IEEE Symposium on

Conference_Location

Kuala Lumpur

Print_ISBN

978-1-4673-2205-8

Type

conf

DOI

10.1109/ISRA.2012.6219146

Filename

6219146