Diameter-constrained steiner trees

W. E.I. Ding, Guohui Lin, Guoliang Xue

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Given an edge-weighted undirected graph G = (V, E, c, w), where each edge e E has a non-negative cost c(e) and a non-negative weight w(e), a set S V of terminals and a positive constant D0, we seek a minimum cost Steiner tree in which all terminals appear as leaves and the tree diameter is bounded by D0. Here the tree diameter is the maximum weight of the paths connecting two different leaves in the tree. Such a problem is called the minimum cost diameter-constrained Steiner tree problem. The problem is NP-hard even when the topology of the Steiner tree is fixed. In present paper we focus on this fixed topology restricted version and present a fully polynomial time approximation scheme for computing a minimum cost diameter-constrained Steiner tree.

Original languageEnglish (US)
Pages (from-to)491-502
Number of pages12
JournalDiscrete Mathematics, Algorithms and Applications
Issue number4
StatePublished - Dec 1 2011


  • Diameter-constrained Steiner tree
  • fixed topology
  • fully polynomial time approximation scheme

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Diameter-constrained steiner trees'. Together they form a unique fingerprint.

Cite this