A new evolutionary approach to the degree-constrained minimum spanning tree problem

B. Brand, M. Kahl, S. Sidhu, V. C. Nam, P. V.J. Sriram, S. Jaeckle, F. Thonke, N. Soehendra

Research output: Contribution to journalArticlepeer-review

95 Scopus citations


Finding the degree-constrained minimum spanning tree (d-MST) of a graph is a well-studied NP-hard problem of importance in communications network design and other network-related problems. In this paper we describe some previously proposed algorithms for solving the problem, and then introduce a novel tree construction algorithm called the Randomized Primal Method (RPM) which builds degree-constrained trees of low cost from solution vectors taken as input. RPM is applied in three stochastic iterative search methods: simulated annealing, multistart hillclimbing, and a genetic algorithm. While other researchers have mainly concentrated on finding spanning trees in Euclidean graphs, we consider the more general case of random graph problems. We describe two random graph generators which produce particularly challenging d-MST problems. On these and other problems we find that the genetic algorithm employing RPM outperforms simulated annealing and multistart hillclimbing. Our experimental results provide strong evidence that the genetic algorithm employing RPM finds significantly lower-cost solutions to random graph d-MST problems than rival methods.

Original languageEnglish (US)
Pages (from-to)125-133
Number of pages9
JournalIEEE Transactions on Evolutionary Computation
Issue number2
StatePublished - Jul 2000
Externally publishedYes


  • Degree-constrained minimum spanning tree
  • Evolutionary algorithm
  • Hybrid heuristics
  • Multistart hillclimbing
  • Network design
  • Prim's algorithm
  • Simulated annealing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'A new evolutionary approach to the degree-constrained minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this