On the partial-terminal steiner tree problem

Sun-Yuan Hsieh, Wen Hao Pi

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

5 Citations (Scopus)

Abstract

Given a complete graph G = (V, E) with a length (or cost) function c: E → ℚ≥ and two proper subsets R ⊂ V and R′ ⊆ R, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R′ must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum length in G. The previously best-known approximation ratio of the problem is 2ρ, where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2ρ to 2ρ - ρ/3ρ-2 - ε where ε is some non-negative number.

Original languageEnglish
Title of host publicationProceedings - 9th International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN 2008
Pages173-177
Number of pages5
DOIs
Publication statusPublished - 2008 Aug 15
Event9th International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN 2008 - Sydney, NSW, Australia
Duration: 2008 May 72008 May 9

Publication series

NameProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN

Other

Other9th International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN 2008
CountryAustralia
CitySydney, NSW
Period08-05-0708-05-09

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the partial-terminal steiner tree problem'. Together they form a unique fingerprint.

Cite this