Hybrid Metaheuristics for the Graph Partitioning Problem

TitreHybrid Metaheuristics for the Graph Partitioning Problem
Type de publicationChapitre
TypeOuvrage scientifique
Année2013
LangueAnglais
Pagination157-185
Volume434
Titre de l'ouvrageHybrid Metaheuristics
AuteurBenlic, Una, Hao, Jin-Kao
PaysAllemagne
EditeurSpringer Berlin Heidelberg
VilleBerlin, Heidelberg
ISBN978-3-642-30670-9
Résumé en anglais

The Graph Partitioning Problem (GPP) is one of the most studied NP-complete problems notable for its broad spectrum of applicability such as in VLSI design, data mining, image segmentation, etc. Due to its high computational complexity, a large number of approximate approaches have been reported in the literature. Hybrid algorithms that are based on adaptations of popular metaheuristic techniques have shown to provide outstanding performance in terms of partition quality. In particular, it is the hybrids between well-known metaheuristics and multilevel strategies that report partitions of the minimal cut-size value. However, metaheuristic hybrids generally require more computing time than those based on greedy heuristics which can generate partitions of acceptable quality in a matter of seconds even for very large graphs. This chapter is dedicated to a review on some representative hybrid metaheuristic approaches including genetic local search, basic multilevel search and recent development on hybrid multilevel search.

URL de la noticehttp://okina.univ-angers.fr/publications/ua7145
DOI10.1007/978-3-642-30671-6_6
Collection

Studies in Computational Intelligence

Lien vers le document

http://dx.doi.org/10.1007/978-3-642-30671-6_6