[ROB10] Complexite de la coloration avec preferences dans les graphes bipartis

Conférence Nationale avec comité de lecture : CongrÃƒÂ¨s ROADEF 2010, January 2010,

Auteurs: B. Robillard

motcle:

Résumé: Le probleme de K-coloration avec preferences est une generalisation du probleme de K-coloration classique permettant de modeliser que deux sommets voudraient, si possible, se voir assignes la meme couleur. Ce probleme est evidemment NP-complet pour un nombre de couleurs K >= 3. Des applications reelles, telles que l'allocation de registres d'un compilateur, passent par la resolution de la K-coloration avec preferences (K-CPM) dans des graphes triangules, dont on sait qu'ils sont K-colorables. Le probleme demeure NP-complet dans de tels graphes, mais nombre de processus de resolution se focalisent sur la colorabilite du graphe, plutot que sur les preferences. Nous avons etabli une serie de resultats de complexite pour ce probleme. Il en resulte en particulier que le probleme de K-coloration avec preferences reste NP-complet si les conflits forment un graphe biparti (donc 2-colorable), et ce pour tout K 2. Ainsi, delaisser les preferences au profit de la colorabilite du graphe apparait comme trop approximatif.

Download

BibTeX

@inproceedings {
	ROB10,
	title	=	"{Complexite de la coloration avec preferences dans les graphes bipartis}",
	author	=	" B. Robillard ",
	booktitle	=	"{CongrÃƒÂ¨s ROADEF 2010}",
	year	=	2010,
	month	=	"January",
}