### Abstract

Given a complete graph G = (V,E) with a cost function c : E → ℝ^{+} and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs Σ _{(u,v)∈E(T)}c(u;v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem.

Original language | English |
---|---|

Title of host publication | Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings |

Pages | 274-283 |

Number of pages | 10 |

Publication status | Published - 2007 Oct 29 |

Event | 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 - Shanghai, China Duration: 2007 May 22 → 2007 May 25 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4484 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 |
---|---|

Country | China |

City | Shanghai |

Period | 07-05-22 → 07-05-25 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings*(pp. 274-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4484 LNCS).

}

*Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4484 LNCS, pp. 274-283, 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, Shanghai, China, 07-05-22.

**On the internal steiner tree problem.** / Hsieh, Sun-Yuan; Gao, Huang Ming; Yang, Shih Cheng.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the internal steiner tree problem

AU - Hsieh, Sun-Yuan

AU - Gao, Huang Ming

AU - Yang, Shih Cheng

PY - 2007/10/29

Y1 - 2007/10/29

N2 - Given a complete graph G = (V,E) with a cost function c : E → ℝ+ and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs Σ (u,v)∈E(T)c(u;v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem.

AB - Given a complete graph G = (V,E) with a cost function c : E → ℝ+ and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs Σ (u,v)∈E(T)c(u;v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem.

UR - http://www.scopus.com/inward/record.url?scp=35449001935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35449001935&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:35449001935

SN - 3540725032

SN - 9783540725039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 274

EP - 283

BT - Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings

ER -