Genetic Algorithms for Constrained Tree Problems

摘要

Given an undirected weighted connected graph G = (V, E) with vertex set V, edge set E and a designated vertex r ∈ V, this chapter studies the following constrained tree problems in G. The first problem, called Constrained Minimum Spanning Tree Problem (CMST), asks for a rooted tree T in G that minimizes the total weight of T such that the distance between the r and any vertex v in T is at most a given constant C times the shortest distance between the two vertices in G. The second problem, Constrained Shortest Path Tree Problem (CSPT) requires a rooted tree T in G that minimizes the maximum distance between r and all vertices in V such that the total weight of T is at most a given constant C times the minimum tree weight in G. It is easy to conclude from the literatures that the above problems are NP-hard. This chapter presents efficient genetic algorithms that return (as shown by our experimental results) high quality solutions for those two problems.