Résumé de rapport du LIF

Téléchargement / Download : pdf 140k , ps.gz 164k , bibtex

Abstract

In this note, the mutual exclusion scheduling problem is considered. Given an undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted with chi(G,k). For intervals graphs, the problem is known to be NP-complete even for fixed k >= 4. We prove that if an interval graph or more generally a circular-arc graph G with n vertices admits a coloring such that each colour is used at least k times, then chi(G,k) equals the lower bound ceil(n/k). The proof yields a linear-time algorithm to solve the problem in this case which finds applications in schedules planning. Then, the assertion is extended to the class of triangulated graphs for k <= 3 and disproved for bounded tolerance graphs and co-comparability graphs.

Keywords

Scheduling, colorings, interval graphs, classes of graphs.

Résumé

Dans cette note, un problème d'ordonnancement avec exclusion mutuelle est abordé. Etant donné un graphe non-orienté G et un entier k, le problème consiste à trouver une coloration de G tel que chaque couleur apparaisse au plus k fois. La cardinalité d'une telle coloration est notée chi(G,k). Pour les graphes d'intervalles, le problème est NP-complet même pour une valeur fixée k >= 4. Nous prouvons que si un graphe d'intervalles ou plus généralement un graphe d'arc circulaires G à n sommets admet une coloration telle que chaque couleur est utilisée au moins k fois, alors chi(G,k) égale la borne inférieure ceil(n/k). La preuve fournit un algorithme linéaire pour résoudre le problème dans ce cas qui possède des applications dans la planification d'horaires de travail. Ensuite, ce résultat est étendu à la classe des graphes triangulés pour k <= 3 et réfuté pour les graphes de tolérance bornée et les compléments des graphes de comparabilité.

Mots clés

Ordonnancement, colorations, graphes d'intervalles, classes de graphes.

Bibtex

@TECHREPORT{12-2003,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{Mutual exclusion scheduling with interval graphs and related classes}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {12-2003},
    MONTH	= {May},
    YEAR	= {2003},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/12-2003.html},
}