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

82 Citations (Scopus)

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

Minimum Spanning Tree
Genetic algorithms
Simulated annealing
Random Graphs
Multistart
Hill Climbing
Genetic Algorithm
Simulated Annealing
Telecommunication networks
Costs
Computational complexity
Network Design
Graph in graph theory
NP-hard Problems
Spanning tree
Search Methods
Communication Networks
Euclidean
Generator
Iteration

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

A new evolutionary approach to the degree-constrained minimum spanning tree problem. / Brand, B.; Kahl, M.; Sidhu, S.; Nam, V. C.; Parupudi, Sreeram; Jaeckle, S.; Thonke, F.; Soehendra, N.

In: IEEE Transactions on Evolutionary Computation, Vol. 4, No. 2, 07.2000, p. 125-133.

Research output: Contribution to journalArticle

Brand, B. ; Kahl, M. ; Sidhu, S. ; Nam, V. C. ; Parupudi, Sreeram ; Jaeckle, S. ; Thonke, F. ; Soehendra, N. / A new evolutionary approach to the degree-constrained minimum spanning tree problem. In: IEEE Transactions on Evolutionary Computation. 2000 ; Vol. 4, No. 2. pp. 125-133.
@article{c393c79cfe9d49fbaff0a953bd467f48,
title = "A new evolutionary approach to the degree-constrained minimum spanning tree problem",
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.",
keywords = "Degree-constrained minimum spanning tree, Evolutionary algorithm, Hybrid heuristics, Multistart hillclimbing, Network design, Prim's algorithm, Simulated annealing",
author = "B. Brand and M. Kahl and S. Sidhu and Nam, {V. C.} and Sreeram Parupudi and S. Jaeckle and F. Thonke and N. Soehendra",
year = "2000",
month = "7",
doi = "10.1109/4235.850653",
language = "English (US)",
volume = "4",
pages = "125--133",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

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

AU - Brand, B.

AU - Kahl, M.

AU - Sidhu, S.

AU - Nam, V. C.

AU - Parupudi, Sreeram

AU - Jaeckle, S.

AU - Thonke, F.

AU - Soehendra, N.

PY - 2000/7

Y1 - 2000/7

N2 - 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.

AB - 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.

KW - Degree-constrained minimum spanning tree

KW - Evolutionary algorithm

KW - Hybrid heuristics

KW - Multistart hillclimbing

KW - Network design

KW - Prim's algorithm

KW - Simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=0034225435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034225435&partnerID=8YFLogxK

U2 - 10.1109/4235.850653

DO - 10.1109/4235.850653

M3 - Article

AN - SCOPUS:0034225435

VL - 4

SP - 125

EP - 133

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 2

ER -