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

B. Brand, M. Kahl, S. Sidhu, V. C. Nam, Sreeram Parupudi, S. Jaeckle, F. Thonke, N. Soehendra

Research output: Contribution to journalArticle

83 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 2000
Externally publishedYes

    Fingerprint

Keywords

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

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Artificial Intelligence
  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Safety, Risk, Reliability and Quality

Cite this