Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/20115
Titre: QUORUM-COLORATION OPTIMALE EN TEMPS LINEAIRE POUR LES ARBRES PARFAITS DONT LES SOMMETS DE MEME PROFONDEUR ONT MEME DEGRE
Auteur(s): Boumalha, Wissam
Issad, Asmaa
Sahbi, H. ( Promotrice)
Mots-clés: Quorum-Coloration
Arbre N-aire parfait
sommets quorum
les sommets de même profondeur ont même degré
Date de publication: 5-sep-2022
Editeur: Université Blida 1
Résumé: Une partition = {V1, V2, ..., Ve} de l'ensemble des sommets V d'un graphe G en classes de couleurs V1, avec 1 ≤ i ≤k, est appelée quorum-coloration si pour tout sommet v € V, au moins la moitié des sommets du voisinage fermé N[v] de vont la même couleur que v. La cardinalité maximum d'une quorum-coloration de G est appelée nombre de quorum-coloration de G et est notée par (G). Une quorum-coloration de cardinalité (G) est une coloration de G. La détermination du nombre de quorum-coloration ou la conception d'un algorithme linéaire le calculant dans un arbre N-aire parfait a été posée récemment comme problème ouvert par Sahbi [25]. Dans ce mémoire, nous résolvons ce problème en concevant un algorithme linéaire trouvant une coloration mais aussi le nombre de quorum-coloration de n'importe quel arbre parfait dont les sommets de même profondeur ont le même degré.
Description: ill., Bibliogr. Cote: ma-510-143
URI/URL: https://di.univ-blida.dz/jspui/handle/123456789/20115
Collection(s) :Mémoires de Master

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
Boumalha Wissam et Issad Asmaa.pdf305,47 kBAdobe PDFVoir/Ouvrir


Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.