A genetic algorithm for the biconnectivity augmentation problem

Abstract

In this paper we present a genetic algorithm (GA) for the NP-hard biconnectivity problem for graphs. Suppose a 2-connected, undirected weighted graph G(V,E) and a spanning subset of edges E/sub 0//spl sub/E are given. The goal is to augment set E/sub 0/ with a set AUG/spl sub/E-E/sub 0/ of minimal weight, such that graph G(V,E/sub 0//spl cup/AUG) is biconnected. To our knowledge, this is the first time a GA is applied to this problem. First, a straight-forward "pure" GA improved with caching is introduced, which is then hybridized with a greedy, problem dependent heuristic. The proposed approaches are problem instances with up to 1160 feasible edges. While the pure GA performs well, significantly better solutions can be obtained by the hybrid strategy.