| Titre : |
Proposition d’un nouvel algorithme pour la coloration forte stricte d’un graphe général. Application à la distribution de graphes. |
| Type de document : |
texte imprimé |
| Auteurs : |
Ahmed Reghioua, Auteur ; Meriem Bensouyad, Auteur ; Nousseiba Guidoum, Auteur ; Nousseiba Guidoum, Directeur de thèse |
| Editeur : |
CONSTANTINE [ALGERIE] : Université Frères Mentouri Constantine |
| Année de publication : |
2011 |
| Importance : |
90 f. |
| Format : |
30 cm. |
| Note générale : |
Une copie electronique PDF disponible au BUC. |
| Langues : |
Français (fre) |
| Catégories : |
Informatique
|
| Tags : |
graphe, coloration forte stricte, heuristique, partitionnement |
| Index. décimale : |
004 Traitement de données. Informatique |
| Résumé : |
La coloration de graphes est un problème classique de la théorie des graphes et de
l’optimisation combinatoire. Il s'agit de colorer les sommets d'un graphe afin que deux
sommets adjacents n’aient pas la même couleur. Ce problème a donné lieu à de nombreuses
variantes telles que la coloration forte et coloration forte stricte où une relation de dominance
entre les sommets du graphe est présente.
Généralement, la coloration forte stricte est une coloration propre telle que chaque sommet
du graphe domine au moins une classe de couleurs non vide.
Le problème de la coloration forte stricte étant NP-difficile, l’utilisation des méthodes
exactes pour le résoudre s’avère inapproprié. Les méthodes approchées ou plus exactement les
heuristiques représentent une alternative qui donne de bonnes solutions en un temps de
résolution réduit.
D’autre part, les systèmes en général peuvent être modélisés par des graphes de différentes
natures : orientés, non orientés, arbres….etc. Donc, la vérification de ces systèmes est
souvent menée à un traitement sur les graphes. Cependant, la vérification formelle des
systèmes souffre du problème d’explosion combinatoire (problème d’insuffisance de la
mémoire et celui du temps de calcul) lorsque la taille des systèmes est très grande.
Pour contourner ce problème, la distribution de graphes sur différentes stations de
traitement est une solution adéquate à ce type de problème. La distribution d’un graphe est
son partitionnement en parties, tout en respectant l’équilibre de charge entre elles ainsi que la
minimisation des connexions reliant ces parties. Ce problème est donc difficile et il peut être
vu comme un problème de partitionnement de graphes.
Dans notre travail, nous proposons d’abord un nouvel algorithme glouton qui donne
après son exécution une coloration forte stricte d’un graphe général en un temps polynomial.
Dans la deuxième partie de ce travail, nous proposons pour la 1ère fois d’adapter notre
approche définie pour le problème de coloration forte stricte au problème de la distribution
de graphes dédié à la vérification des systèmes. |
| Diplome : |
Master 2 |
| Permalink : |
https://bu.umc.edu.dz/master/index.php?lvl=notice_display&id=7746 |
Proposition d’un nouvel algorithme pour la coloration forte stricte d’un graphe général. Application à la distribution de graphes. [texte imprimé] / Ahmed Reghioua, Auteur ; Meriem Bensouyad, Auteur ; Nousseiba Guidoum, Auteur ; Nousseiba Guidoum, Directeur de thèse . - CONSTANTINE [ALGERIE] : Université Frères Mentouri Constantine, 2011 . - 90 f. ; 30 cm. Une copie electronique PDF disponible au BUC. Langues : Français ( fre)
| Catégories : |
Informatique
|
| Tags : |
graphe, coloration forte stricte, heuristique, partitionnement |
| Index. décimale : |
004 Traitement de données. Informatique |
| Résumé : |
La coloration de graphes est un problème classique de la théorie des graphes et de
l’optimisation combinatoire. Il s'agit de colorer les sommets d'un graphe afin que deux
sommets adjacents n’aient pas la même couleur. Ce problème a donné lieu à de nombreuses
variantes telles que la coloration forte et coloration forte stricte où une relation de dominance
entre les sommets du graphe est présente.
Généralement, la coloration forte stricte est une coloration propre telle que chaque sommet
du graphe domine au moins une classe de couleurs non vide.
Le problème de la coloration forte stricte étant NP-difficile, l’utilisation des méthodes
exactes pour le résoudre s’avère inapproprié. Les méthodes approchées ou plus exactement les
heuristiques représentent une alternative qui donne de bonnes solutions en un temps de
résolution réduit.
D’autre part, les systèmes en général peuvent être modélisés par des graphes de différentes
natures : orientés, non orientés, arbres….etc. Donc, la vérification de ces systèmes est
souvent menée à un traitement sur les graphes. Cependant, la vérification formelle des
systèmes souffre du problème d’explosion combinatoire (problème d’insuffisance de la
mémoire et celui du temps de calcul) lorsque la taille des systèmes est très grande.
Pour contourner ce problème, la distribution de graphes sur différentes stations de
traitement est une solution adéquate à ce type de problème. La distribution d’un graphe est
son partitionnement en parties, tout en respectant l’équilibre de charge entre elles ainsi que la
minimisation des connexions reliant ces parties. Ce problème est donc difficile et il peut être
vu comme un problème de partitionnement de graphes.
Dans notre travail, nous proposons d’abord un nouvel algorithme glouton qui donne
après son exécution une coloration forte stricte d’un graphe général en un temps polynomial.
Dans la deuxième partie de ce travail, nous proposons pour la 1ère fois d’adapter notre
approche définie pour le problème de coloration forte stricte au problème de la distribution
de graphes dédié à la vérification des systèmes. |
| Diplome : |
Master 2 |
| Permalink : |
https://bu.umc.edu.dz/master/index.php?lvl=notice_display&id=7746 |
|
Affiner la rechercheÉtude de l’impact du COVID-19 sur l’hygiène et la sécurité au sein de l’entreprise Algérienne : NAFTAL / Nadjete Maassem
