Hardness and approximation of the selected-leaf-terminal steiner tree problem

Sun-Yuan Hsieh, Huang Ming Gao

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

Abstract

For a complete graph G = (V, E) with length function l : E → R + and two vertex subsets R C V and R' C R, a selected-leaf-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R\ R' belong to the leaves of this Steiner tree. The selected-leaf-terminal Steiner tree problem is to find a selected-leaf-terminal Steiner tree T whose total lengths Σ(v,v)εT(u,v) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem.

Original languageEnglish
Title of host publicationProceedings - Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2006
Pages565-568
Number of pages4
DOIs
Publication statusPublished - 2006 Dec 1
Event7th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2006 - Taipei, Taiwan
Duration: 2006 Dec 42006 Dec 7

Publication series

NameParallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

Other

Other7th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2006
CountryTaiwan
CityTaipei
Period06-12-0406-12-07

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Hardness and approximation of the selected-leaf-terminal steiner tree problem'. Together they form a unique fingerprint.

Cite this