Authors: Ljubić, Ivana
Raidl, Giinther R.
Kratica, Jozef 
Title: A hybrid ga for the edge-biconnectivity augmentation problem
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 1917
First page: 641
Last page: 650
Conference: 6th International Conference on Parallel Problem Solving from Nature, PPSN 2000; Paris; France; 18 September 2000 through 20 September 2000
Issue Date: 1-Jan-2000
Rank: M23
ISBN: 978-3-540-45356-7
ISSN: 0302-9743
DOI: 10.1007/3-540-45356-3_63
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 A/’P-complete edge-biconnectivity augmentation (E2AUG) problem, in which a given graph Go(V, Eo) needs to be augmented by the cheapest possible set of edges A UG so that a single edge deletion does not disconnect Go. The new approach is based on a preliminary 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 first, more traditional variant, infeasible solutions are detected and simply discarded. The second method is a hybrid approach that uses an effective heuristic to repair infeasible solutions by adding usually cheap edges to A UG until the graph augmented with AUG becomes edge-biconnected. The two G A-variants are empirically compared to each other and to another iterative heuristic for the E2AUG problem using instances involving up to 1270 edges.
Publisher: Springer Link

Show full item record


checked on Jun 24, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.