NEW METAHEURISTIC APPROACHES FOR THE LEAF-CONSTRAINED MINIMUM SPANNING TREE PROBLEM

Alok Singh () and Anurag Singh Baghel ()
Additional contact information
Alok Singh: Department of Computer and Information Sciences, School of Mathematics and Computer/Information Sciences, University of Hyderabad, Hyderabad – 500046, Andhra Pradesh, India
Anurag Singh Baghel: Department of Electronics and Communication, Banasthali Vidyapith Jaipur Campus, Sarojini Marg, Jaipur – 302001, Rajasthan, India

Asia-Pacific Journal of Operational Research (APJOR), 2008, vol. 25, issue 04, 575-589

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

Keywords: Ant-colony optimization; combinatorial optimization; leaf-constrained minimum spanning tree; subset coding; tabu search (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595908001870
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:25:y:2008:i:04:n:s0217595908001870

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595908001870

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().