On the internal steiner tree problem

Sun Yuan Hsieh, Huang Ming Gao, Shih Cheng Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

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 languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings
PublisherSpringer Verlag
Pages274-283
Number of pages10
ISBN (Print)3540725032, 9783540725039
DOIs
Publication statusPublished - 2007
Event4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 - Shanghai, China
Duration: 2007 May 222007 May 25

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4484 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Conference on Theory and Applications of Models of Computation, TAMC 2007
Country/TerritoryChina
CityShanghai
Period07-05-2207-05-25

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On the internal steiner tree problem'. Together they form a unique fingerprint.

Cite this