DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ljubić, Ivana | en |
dc.contributor.author | Raidl, Giinther R. | en |
dc.contributor.author | Kratica, Jozef | en |
dc.date.accessioned | 2020-04-26T19:14:57Z | - |
dc.date.available | 2020-04-26T19:14:57Z | - |
dc.date.issued | 2000-01-01 | en |
dc.identifier.isbn | 978-3-540-45356-7 | en |
dc.identifier.issn | 0302-9743 | en |
dc.identifier.uri | http://researchrepository.mi.sanu.ac.rs/handle/123456789/513 | - |
dc.description.abstract | 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. | en |
dc.publisher | Springer Link | - |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en |
dc.title | A hybrid ga for the edge-biconnectivity augmentation problem | en |
dc.type | Article | en |
dc.relation.conference | 6th International Conference on Parallel Problem Solving from Nature, PPSN 2000; Paris; France; 18 September 2000 through 20 September 2000 | - |
dc.identifier.doi | 10.1007/3-540-45356-3_63 | - |
dc.identifier.scopus | 2-s2.0-84947915321 | en |
dc.relation.firstpage | 641 | en |
dc.relation.lastpage | 650 | en |
dc.relation.volume | 1917 | en |
dc.description.rank | M23 | - |
item.grantfulltext | none | - |
item.cerifentitytype | Publications | - |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.openairetype | Article | - |
crisitem.author.orcid | 0000-0002-9752-0971 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.