Cellular Competitive Decision Algorithm for Degree-Constrained Minimum Spanning tree Problem
Xiong Xiao · Journal of Shanghai Second Polytechnic University · 2011
Finding the Degree-Constrained Minimum Spanning Tree(DCMST for short) of a graph is a classical combinatorial optimization hard problem in network-designing and optimization.Competitive decision algorithm(CDA for short) is a new type algorithm especially suitable for solving combinatorial optimization problems.Cellular competitive decision algorithm for DCMST is presented here to improve the accuracy of the solution,which introduced the neighborhood evolution of cellular automata into CDA.To speed up the algorithm,the mathematical properties of DMST are used to reduce the scale of instances.To verify the effectiveness of the algorithm,it is being coded in Delphi 7.0 and series of instances are tested here.