Ivana Ljubiæ
Günther R. Raidl
Jozef Kratica
In the design of communication networks, robustness against failures in single links or nodes is an important issue. This paper proposes a new approach for the NP-complete edge-biconnectivity augmentation (E2AUG) problem, in which a given graph G (V;E) needs to be aug- mented by the cheapest possible set of edges AUG so that a single edge deletion does not disconnect G. The new approach is based on a pre- liminary reduction of the problem and a genetic algorithm (GA) using a binary vector to represent a set of augmenting edges and therefore a candidate solution. Two strategies are proposed to deal with infeasible solutions that do not lead to edge-biconnectivity. In the rst, more tra- ditional variant, infeasible solutions are detected and simply discarded. The second method is a hybrid approach that uses an e ective heuris- tic to repair infeasible solutions by adding usually cheap edges to AUG until the graph augmented with AUG becomes edge-biconnected. The two GA-variants are empirically compared to each other and to another iterative heuristic for the E2AUG problem using instances involving up to 1270 edges.
Back to Jozef's Papers Home Page | Back to Jozef's Home Page | Go to PPSN 2000 Conference Home Page | Connectivity Augmentation Problems in Graphs