Abstract:

Both multi-criteria minimum spanning tree problem and degree-constrained minimum spanning tree problem are NP-hard problems in network optimization.They always have many important applications in practice.To solve the minimum spanning tree problem by considering both the multi-criteria and degreeconstraints, this paper proposes an algorithm (coded in Delphi)which is based on the ideas of ant colony optimization. The computational numerical experiments show the efficiency and effectiveness of the algorithm for the multi-criteria degree-constrained minimum spanning tree problem.

Key words: Multi-criteria, Degree-constraint, Minimum spanning tree, Ant colony optimization