Authors: Ljubić, Ivana
Kratica, Jozef 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: A genetic algorithm for the biconnectivity augmentation problem
Journal: Proceedings of the 2000 Congress on Evolutionary Computation, CEC 2000
Volume: 1
First page: 89
Last page: 96
Conference: 2000 Congress on Evolutionary Computation, CEC 2000; San Diego, CA; United States; 16 July 2000 through 19 July 2000
Issue Date: 1-Jan-2000
Rank: M30
DOI: 10.1109/CEC.2000.870280
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.
Publisher: IEEE

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.