Algorithmic aspects of graph colourings heuristics

Leonardo Sampaio 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.
Type de document :
Thèse
Data Structures and Algorithms [cs.DS]. Université Nice Sophia Antipolis, 2012. English


https://tel.archives-ouvertes.fr/tel-00759408
Contributeur : Leonardo Sampaio <>
Soumis le : vendredi 30 novembre 2012 - 15:34:59
Dernière modification le : vendredi 30 novembre 2012 - 15:45:50
Document(s) archivé(s) le : vendredi 1 mars 2013 - 03:56:00

Identifiants

  • HAL Id : tel-00759408, version 1

Collections

Citation

Leonardo Sampaio. Algorithmic aspects of graph colourings heuristics. Data Structures and Algorithms [cs.DS]. Université Nice Sophia Antipolis, 2012. English. <tel-00759408>

Exporter

Partager

Métriques

Consultations de
la notice

529

Téléchargements du document

687