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 journalArticle

84 Scopus citations

Abstract

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
Volume4
Issue number2
DOIs
StatePublished - Jul 1 2000

Keywords

  • 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

Fingerprint 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