A branch-and-bound algorithm for computing node weighted steiner minimum trees

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


Given n regular points in the Euclidean plane, the node-weighted Steiner minimum tree (NWSMT) is a straight line network interconnecting these n regular points and some Steiner points with a minimum cost, where the cost of the network is the sum of the edge lengths plus the total cost of the Steiner points. In 1995, [11] proved that a tight upper bound on the maximum degree of Steiner points in a NWSMT is 4. In 1996, [14] used this result to propose a modified Melzak procedure for computing a NWSMT. However, that procedure requires exponential time to compute a minimum cost network under a given topology. In this paper, we prove that there exists a NWSMT in which the maximum degree of regular points is no more than 5 and that this upper bound is tight. For a given topology interconnecting n regular points, we show that the Xue-Ye algorithm [15] for minimizing a sum of Euclidean norms can be used to compute an (1 + ε)-approximation of the minimum cost network in n1.5(log n + log 1/ε time for any positive ε. These results enable an algorithm that computes a NWSMT by enumerating all the possible Steiner topologies. We prove a bounding theorem that can be used in a branch-and-bound algorithm and present preliminary computational experience.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings
EditorsTao Jiang, D.T. Lee
PublisherSpringer Verlag
Number of pages10
ISBN (Print)354063357X, 9783540633570
StatePublished - 1997
Externally publishedYes
Event3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China
Duration: Aug 20 1997Aug 22 1997

Publication series

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


Other3rd Annual International Computing and Combinatorics Conference, COCOON 1997


  • Branch-and-bound
  • Maximum node degrees
  • Minimum cost network under a given topology
  • Node weighted Steiner minimum trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A branch-and-bound algorithm for computing node weighted steiner minimum trees'. Together they form a unique fingerprint.

Cite this