Partitionnement de Graphe

• Main Authors: DEVILLE, Yves, DUONG, Khanh Chuong
• Format: Theses and Dissertations
• Language: French
• Published: 2015
• Subjects: partition; recherche locale; multi-niveaux; contraction; affinage
• Online Access: http://repository.vnu.edu.vn/handle/VNU_123/318
• Institution: Vietnam National University, Hanoi

Le problème du partitionnement de graphe a pour but de découper un graphe en différentes parties (partitions) qui satisfont certains contraintes (telle que l’équilibre des parties) et qui optimisent une certaines fonction objectif (telle que le coût de coup). Il possède de nombreuses applications comme la conception de circuits intégrés électroniques, la répartition de charge pour les machines parallèles ou la segmentation d’images. Cependant, le partitionnement de graphe est un problème complexe (NP-complet), dont la solution ne peut pas être trouvée au moyen d’une méthode de résolution exacte. Pour ce type de problème, la recherche locale est une approche adéquate. Dans ce travail, nous avons étudié et analysé des méthodes de partitionnement classiques comme la méthode de glouton, le multi-niveaux ou les algorithmes de type Kernighan-Lin et des méthodes de recherche locale comme la recherche taboue et le recuit simulé. Enfin, nous avons implémenté les méthodes présentées dans ce mémoire dans COMET, et nous avons comparé leur performance et leur efficacité avec le logiciel METIS.