| Titre : | Algorithmes exacts de coloriage de graphes pour l'ordonnancement | | Type de document : | texte manuscrit | | Auteurs : | Attia Nehar, Auteur ; Hadda Cherroun, Directeur de thèse | | Editeur : | Laghouat : Université Amar Telidji - Département d'informatique | | Année de publication : | 2013 | | Importance : | 78 p. | | Format : | 30 cm. | | Accompagnement : | 1 disque optique numérique (CD-ROM) | | Note générale : | Option : Ingénierie des systèmes informatiques | | Langues : | Français | | Catégories : | THESES :10 informatique
| | Mots-clés : | Algorithmes Coloriage de graphes 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é que le problème de calcul de clique maximale est NP-complet, l'algorithme a prouvé son efficacité pour les instances de graphes petites et moyennes. Cependant, son temps d’exécution 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 efficace et rapide utilisant ainsi une plateforme et un langage appropriés.
En effet, 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 affirment la qualité de cette amélioration. | | note de thèses : | Thèse de magister en informatique |
Algorithmes exacts de coloriage de graphes pour l'ordonnancement [texte manuscrit] / Attia Nehar, Auteur ; Hadda Cherroun, Directeur de thèse . - Laghouat : Université Amar Telidji - Département d'informatique, 2013 . - 78 p. ; 30 cm. + 1 disque optique numérique (CD-ROM). Option : Ingénierie des systèmes informatiques Langues : Français | Catégories : | THESES :10 informatique
| | Mots-clés : | Algorithmes Coloriage de graphes 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é que le problème de calcul de clique maximale est NP-complet, l'algorithme a prouvé son efficacité pour les instances de graphes petites et moyennes. Cependant, son temps d’exécution 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 efficace et rapide utilisant ainsi une plateforme et un langage appropriés.
En effet, 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 affirment la qualité de cette amélioration. | | note de thèses : | Thèse de magister en informatique |
|
Algorithmes exacts de coloriage de graphes pour l'ordonnancement
