Genetic Algorithms for Balanced Spanning Tree Problem

Given an undirected weighted connected graph G = (V, E) with vertex set V and edge set E and a designated vertex r is an element of V, we consider the problem of constructing a spanning tree in G that balances both the minimum spanning tree and the shortest paths tree rooted at r. Formally, for any two constants a, alpha, beta >= 1, we consider the problem of computing an (alpha, beta)-balanced spanning tree T in G, in the sense that, (i) for every vertex v is an element of V, the distance between r and v in T is at most alpha times the shortest distance between the two vertices in G, and (ii) the total weight of T is at most beta times that of the minimum tree weight in G. It is well known that, for any alpha, beta >= 1, the problem of deciding whether G contains an (alpha, beta)-balanced spanning tree is NP-complete [ 15]. Consequently, given any alpha >= 1 (resp., beta >= 1), the problem of finding an (alpha, beta)-balanced spanning tree that minimizes beta (resp., alpha) is NP-complete. In this paper, we present efficient genetic algorithms for these problems. Our experimental results show that the proposed algorithm returns high quality balanced spanning trees.