Approximating Internal Steiner Forest
Date Issued
2009
Date
2009
Author(s)
Liu, Wei-Yang
Abstract
Given a complete graph G = (V,E) with metric weight function c : E → R+ and a list R = {R1,R2, ...,Rk} of disjoint vertex subset of V , an internal Steiner forest problem is seek a Steiner forest such that the vertices in Ri are connected with each other and restricted to be internal vertex for this forest. Suppose ρ′ is the approximation ratio for the Steiner forest problem, and m is the number of connected component. we give a approximation ratio 2ρ′ + 4 logm for this problem. If k = 1, this problem is an internal Steiner tree problem, due to Hsieh. Suppose ρ is the approximation ratio for the Steiner tree problem, the previous result of an internal Steiner tree problem is 2ρ + 1 and we also obtain an approximation ratio 2ρ. Moreover, if our result graph allow to have cycle in the above problem, we address this case as internal Steiner subgraph problem and also give an approximation ratio.
Subjects
Steiner tree
Steiner forest
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R94944030-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):b008d78ab07d36e6b879e9d51ac7932a