Genetic Programming Based Degree Constrained Spanning Tree Extraction

Abstract—The problem of extracting a degree constraint spanning tree deals with extraction of a spanning tree from a given graph. Where, the degree of each node is greater than or equal to a thread hold value. Genetic Programming is an evolution based strategy appropriate for optimization problems. In this paper we propose a genetic programming based solution to the degree constraint spanning tree extraction. The individuals of the population are represented as a tree and mutation is applied as the only genetic operator for evaluation to occur. We have further tested our proposed solution on different graph and found it to be suitable for degree constraint spanning tree extraction proble