Approximating Internal Steiner Forest
| Autor: | Wei-Yang Liu, 劉偉揚 |
|---|---|
| Rok vydání: | 2009 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 97 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|