Ivana Ljubiæ
Jozef Kratica
In this paper we present a genetic algorithm (GA) for the NP-hard biconnectivity augmentation problem for graphs. Suppose a 2-connected, undirected weighted graph G(V,E) and a spanning subset of edges E0 Ì E are given. The goal is to augment set E0 with a set AUGÌ E-E0 of minimal weight, such that graph G(V,E0È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 tested on problem instances with up to 1160 feasible edges. While the pure GA performs well, significantly better solutions can be obtained by the hybrid strategy.
Back to Jozef's Papers Home Page | Back to Jozef's Home Page | Talk - fol. PDF (184 KB) | CEC Program | Go to Conference home page | Connectivity Augmentation Problems in Graphs