Accéder directement au contenu Accéder directement à la navigation
Chapitre d'ouvrage

Hybrid Metaheuristics for the Graph Partitioning Problem

Abstract :

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.

Type de document :
Chapitre d'ouvrage
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03256232
Contributeur : Okina Université d'Angers <>
Soumis le : jeudi 10 juin 2021 - 10:32:46
Dernière modification le : vendredi 11 juin 2021 - 03:29:59

Lien texte intégral

Identifiants

Collections

Citation

Una Benlic, Jin-Kao Hao. Hybrid Metaheuristics for the Graph Partitioning Problem. Hybrid Metaheuristics, 434, Springer Berlin Heidelberg, pp.157-185, 2013, Studies in Computational Intelligence, 978-3-642-30670-9. ⟨10.1007/978-3-642-30671-6_6⟩. ⟨hal-03256232⟩

Partager

Métriques

Consultations de la notice

4