loading...
On the Partial-Terminal Steiner Tree Problem
May 07-May 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2008.11The International Symposium on Parall ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Sun-Yuan Hsieh, Wen-Hao Pi, "On the Partial-Terminal Steiner Tree Problem," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 173-177, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008.
 
 
BibTex
x
 
@article{ 10.1109/I-SPAN.2008.11,
author = {Sun-Yuan Hsieh and Wen-Hao Pi},
title = {On the Partial-Terminal Steiner Tree Problem},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2008},
isbn = {978-0-7695-3125-0},
pages = {173-177},
doi = {http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2008.11},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - On the Partial-Terminal Steiner Tree Problem
SN - 978-0-7695-3125-0
SP173
EP177
A1 - Sun-Yuan Hsieh,
A1 - Wen-Hao Pi,
PY - 2008
KW - The Steiner tree problem
KW - the partial-terminal Steiner tree problem
KW - MAX SNP-hardness
KW - approximation algorithms.
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Given a complete graph G = (V,E) with a length (or cost) function c : E ? Q≥ and two proper subsets R ? V and R? ? R, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R? must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum length in G. The previously best-known approximation ratio of the problem is 2ρ, where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2ρ to 2ρ − (ρ/3ρ−2) − ?, where ? is some non-negative number.
Index Terms:
The Steiner tree problem, the partial-terminal Steiner tree problem, MAX SNP-hardness, approximation algorithms.
Citation:
Sun-Yuan Hsieh, Wen-Hao Pi, "On the Partial-Terminal Steiner Tree Problem," ispan, pp.173-177, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.