An Improved Ant-Based Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

Author

Bui, Thang N. ; Deng, Xianghua ; Zrncic, Catherine M.

Author_Institution

Dept. of Math. & Comput. Sci., Pennsylvania State Univ. at Harrisburg, Middletown, PA, USA

Volume

16

Issue

2

fYear

2012

fDate

4/1/2012 12:00:00 AM

Firstpage

266

Lastpage

278

Abstract

The degree-constrained minimum spanning tree (DCMST) problem is the problem of finding the minimum cost spanning tree in an edge weighted complete graph such that each vertex in the spanning tree has degree ≤ d for some d ≥ 2. The DCMST problem is known to be NP-hard. This paper presents an ant-based algorithm to find low cost degree-constrained spanning trees (DCST). The algorithm employs a set of ants which traverse the graph and identify a set of candidate edges, from which a DCST is constructed. Local optimization algorithms are then used to further improve the DCST. Extensive experiments using 612 problem instances show many improvements over existing algorithms.

Keywords

ant colony optimisation; graph theory; trees (mathematics); DCMST; NP-hard; degree-constrained minimum spanning tree problem; edge weighted complete graph; improved ant-based algorithm; local optimization algorithms; minimum cost spanning tree; Ant colony optimization; Data structures; Encoding; Genetic algorithms; Polynomials; Simulated annealing; Ant-based algorithm; degree constrained spanning tree;

fLanguage

English

Journal_Title

Evolutionary Computation, IEEE Transactions on

Publisher

ieee

ISSN

1089-778X

Type

jour

DOI

10.1109/TEVC.2011.2125971

Filename

5910378