New metaheuristic approaches for the leaf-constrained minimum spanning tree problem

New metaheuristic approaches for the leaf-constrained minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor200962749
Country: Singapore
Volume: 25
Issue: 4
Start Page Number: 575
End Page Number: 589
Publication Date: Aug 2008
Journal: Asia-Pacific Journal of Operational Research
Authors: ,
Keywords: heuristics, heuristics: ant systems, heuristics: tabu search
Abstract:

Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a spanning tree of the graph with smallest weight among all spanning trees of the graph, which contains at least l leaves. In this paper we have proposed two new metaheuristic approaches for the LCMST problem. One is an ant-colony optimization (ACO) algorithm, whereas the other is a tabu search based algorithm. Similar to a previously proposed genetic algorithm, these metaheuristic approaches also use the subset coding that represents a leaf-constrained spanning tree by the set of its interior vertices. Our new approaches perform well in comparison with two best heuristics reported in the literature for the problem – the subset-coded genetic algorithm and a greedy heuristic.

Reviews

Required fields are marked *. Your email address will not be published.