Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/674
Title: Solving the maximally balanced connected partition problem in graphs by using genetic algorithm
Authors: Djurić, Brankica
Kratica, Jozef
Tošić, Dušan
Filipović, Vladimir 
Affiliations: Informatics and Computer Science 
Keywords: Balanced partitions;Combinatorial optimization;Evolutionary computation;Metaheuristics
Issue Date: 1-Jan-2008
Journal: Computing and Informatics
Abstract: 
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.
URI: https://research.matf.bg.ac.rs/handle/123456789/674
ISSN: 13359150
Appears in Collections:Research outputs

Show full item record

SCOPUSTM   
Citations

18
checked on Dec 18, 2024

Page view(s)

11
checked on Dec 23, 2024

Google ScholarTM

Check


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