On the internal steiner tree problem

Sun-Yuan Hsieh, Huang Ming Gao, Shih Cheng Yang

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

2 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
Pages274-283
Number of pages10
Publication statusPublished - 2007 Oct 29
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
CountryChina
CityShanghai
Period07-05-2207-05-25

Fingerprint

Steiner Tree Problem
Approximation algorithms
Cost functions
Steiner Tree
Internal
Costs and Cost Analysis
Single Nucleotide Polymorphism
Costs
Vertex of a graph
Best Approximation
Complete Graph
Cost Function
Approximation Algorithms
Subset
Approximation

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hsieh, S-Y., Gao, H. M., & Yang, S. C. (2007). On the internal steiner tree problem. In 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).
Hsieh, Sun-Yuan ; Gao, Huang Ming ; Yang, Shih Cheng. / On the internal steiner tree problem. Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings. 2007. pp. 274-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{800bc013bc8e4f209149dcc63a7e151f,
title = "On the internal steiner tree problem",
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.",
author = "Sun-Yuan Hsieh and Gao, {Huang Ming} and Yang, {Shih Cheng}",
year = "2007",
month = "10",
day = "29",
language = "English",
isbn = "3540725032",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "274--283",
booktitle = "Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings",

}

Hsieh, S-Y, Gao, HM & Yang, SC 2007, On the internal steiner tree problem. in 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.

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Hsieh S-Y, Gao HM, Yang SC. On the internal steiner tree problem. In Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings. 2007. p. 274-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).