A comparison of Two Stochastic Iterative Search Techniques for Degree Constrained Minimum Spanning Tree

Degree Constrained Minimum Spanning Tree (d-MST), is a well studied NP-hard problem. In practice this problem arises in communication, transportation and sensor networks. The degree constraint of a vertex represents, the highest number of wires or roads possible at that vertex and the minimum length of wires or roads required to connect all the vertices or nodes, is sought. In this peper a genetic algorithm (GA) and an evolutionary algorithm (EA) have been implemented, compared, and analyzed. Experimental data shows that the performance of GA is depended on the random function used and on its initial population. EA against an exact algorithm (d-Prim) on the basis of weight, runtime and degree bound has been compared, which shows, the weaknesses and superiority of evolutionary algorithms in general.