We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem.
- Authors
Singh, Kavita; Sundar, Shyam
- Abstract
Given an undirected, connected, edge-weighted graph G and a positive integer d, the degree-constrained minimum spanning tree (dc-MST) problem aims to find a minimum spanning tree T on G subject to the constraint that each vertex is either a leaf vertex or else has degree at most d in T, where d is a given positive integer. The dc-MST is NP -hard problem for d ≥ 2 and finds several real-world applications. This paper proposes a hybrid approach (H SSGA) combining a steady-state genetic algorithm and local search strategies for the this problem. An additional step (based on perturbation strategy at a regular interval of time) in the replacement strategy is applied in order to maintain diversity in the population throughout the search process. On a set of available 107 benchmark instances, computational results show the superiority of our proposed H SSGA in comparison with the state-of-the-art metaheuristic techniques.
- Subjects
SPANNING trees; GENETIC algorithms; GRAPH algorithms; APPROXIMATION algorithms
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2020, Vol 24, Issue 3, p2169
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-019-04051-x