loading
Sách, tuyển tập

Partitionnement de Graphe / DUONG, Khanh Chuong

Tác giả : DUONG, Khanh Chuong

Năm xuất bản : 2009

Chủ đề : 1. affinage. 2. contraction. 3. multi-niveaux. 4. partition. 5. recherche locale. 6. Thesis.

Chia sẻ

Thông tin chi tiết

Tóm tắt :

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.
Chia sẻ


Hiển thị MARC

 Thông tin dữ liệu nguồn

 Thư viện  Ký hiệu xếp giá  Dữ liệu nguồn
Viện Quốc tế Pháp ngữ - ĐHQGHN
https://repository.vnu.edu.vn/handle/VNU_123/318