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.
Recommended Citation
Yeh, Chun-Chao and Chien, Ying-Che
(2014)
"A PARTICLE SWARM OPTIMIZATION-LIKE ALGORITHM FOR CONSTRAINED MINIMAL SPANNING TREE PROBLEMS,"
Journal of Marine Science and Technology: Vol. 22:
Iss.
3, Article 8.
DOI: 10.6119/JMST-013-1119-2
Available at:
https://jmstt.ntou.edu.tw/journal/vol22/iss3/8
