A Memetic Algorithm for Minimum-Cost Vertex-Biconnectivity Augmentation of Graphs |
| |
Authors: | Ivana Ljubić Günther R Raidl |
| |
Institution: | (1) Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße, 9–11/186, 1040 Vienna, Austria |
| |
Abstract: | This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph vertex-biconnected. A real-world instance of this problem is the enhancement of an already established computer network to become robust against single node failures. The presented memetic algorithm includes effective preprocessing of problem data and a fast local improvement strategy which is applied before a solution is included into the population. In this way, the memetic algorithm's population consists always of only feasible, locally optimal solution candidates. Empirical results on two sets of test instances indicate the superiority of the new approach over two previous heuristics and an earlier genetic algorithm. |
| |
Keywords: | vertex-biconnectivity connectivity augmentation network survivability memetic algorithm evolutionary computation |
本文献已被 SpringerLink 等数据库收录! |