A PARTICLE SWARM OPTIMIZATION-LIKE ALGORITHM FOR CONSTRAINED MINIMAL SPANNING TREE PROBLEMS

Abstract

Previous studies have discussed various constrained minimal spanning tree (MST) problems. In this paper, we propose an efficient algorithm for solving a class of constrained MST problems. The proposed PSO (Particle Swarm Optimization)-like strategy for solving constrained MST problems identifies optimal MSTs under degree and delay constraints. The solution quality and computation time of the proposed PLCMST (PSO-Like algorithm for Constrained MST problems) algorithm is compared with two other algorithms: one based on ant colony optimization, and the other based on a genetic algorithm strategy. Our experimental results show that the PLCMST outperforms the other two approaches, particularly when using dense graphs.