Authors: Đurić, Brankica
Kratica, Jozef 
Tošić, Dušan
Filipović, Vladimir
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Solving the maximally balanced connected partition problem in graphs by using genetic algorithm
Journal: Computing and Informatics
Volume: 27
Issue: 3
First page: 341
Last page: 354
Issue Date: 21-Jul-2008
Rank: M23
ISSN: 1335-9150
This paper exposes a research of the NP-hard Maximally Balanced Connected Partition problem (MBCP). The proposed solution comprises of a genetic algorithm (GA) that uses: binary representation, fine-grained tournament selection, one-point crossover, simple mutation with frozen genes and caching technique. In cases of unconnected partitions, penalty functions are successfully applied in order to obtain the feasible individuals. The effectiveness of presented approach is demonstrated on the grid graph instances and on random instances with up to 300 vertices and 2000 edges.
Keywords: Balanced partitions | Combinatorial optimization | Evolutionary computation | Metaheuristics
Publisher: Slovak Academy of Sciences
Project: Serbian Ministry of Science and Ecology, project 144007

Show full item record


checked on May 23, 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.