Mémoires de Fin d’Etudes
Etablissement
Université de Laghouat - Amar Telidji
Affiliation
Département d’Informatique
Auteur
NEHAR, Attia
Directeur de thèse
Cherroun.Hadda (Maitre de conférence)
Filière
Informatique
Diplôme
Magister
Titre
Algorithmes exacts de Coloriage de Graphes pour l’Ordonnancement
Mots clés
Coloriage de graphe, Ordonnancement, Branch-And-Bound, Nombre chromatique, Nombre de clique, Fonction thêta.
Résumé
Dans ce mémoire, on aborde le problème de l’ordonnancement basé sur le coloriage de graphes. Malgré que dans la littérature, plusieurs méthodes de coloriage exact existent, ce problème présente jusqu’aujourd’hui un vrai challenge théorique. Pour cela, dans le contexte de calcul d’ordonnancement, un algorithme exact de coloriage de graphes a été proposé [11]. Cet algorithme se base sur le schéma par séparation et évaluation (branch-and-bound). La méthode de séparation s’appuie sur une idée de Béla Bollobàs, qui permet de transformer progressivement un graphe quelconque en un graphe complet dont le coloriage est évident. La méthode d’évaluation s’appuie sur le calcul de clique maximale. Malgrès que le problème de calcul de clique maximale est NP-complet, l’algorithme a prouvé son e cacité pour les instances de graphes petites et moyennes. Cependant, son temps d’execution devient trés grand pour le cas général, c.à.d pour des graphes de taille considérable, notamment, ceux modélisant des applications de taille plus importante. L’objectif de ce travail est double, il s’agit d’analyser cet algorithme dans le but de l’améliorer, spé- cialement en remplaçant la méthode d’évaluation par une autre méthode moins coûteuse, puis d’évaluer ses performances par une implémentation e cace et rapide utilisant ainsi une plateforme et un langage appropriés. En e et, nous avons amélioré l’ordonnanceur considéré en instrumentant la fonction thêta : une nouvelle borne inférieure au nombre chromatique. Les résultats a rment la qualité de cette amélioration.
Date de soutenance
2011
Cote
THL10.200
Pagination
77p
Illusatration
ill.;fig.;tabl.
Notes
Bibliogr.Annexes
Statut
Soutenue