Résumé de rapport du LIF

Téléchargement / Download : pdf 172k , ps.gz 200k , bibtex

Abstract

In this paper, the mutual exclusion scheduling (MES) problem for proper interval graphs is considered. Given an undirected graph G and a non-negative integer k, the problem is to find a minimum coloring of G, such that each colour is used at most k times. The complexity of this problem is known to be NP-complete for interval graphs. We prove that MES can be solved in linear time for proper interval graphs thanks to a greedy algorithm. As a byproduct of the proof of this result, we also obtain a linear-time algorithm to solve MES for interval graphs under certain conditions. Finally, this study yields some results about the complexity of finding an uniform coloring of proper interval graphs.

Keywords

Mutual exclusion scheduling, working schedules planning, proper interval graphs, colorings, linear-time algorithms.

Résumé

Dans ce papier, le problème "Mutual Exclusion Scheduling" (MES) pour les graphes d'intervalles propres est considéré. Etant donné un graphe G non-orienté et un entier naturel k, le problème est de trouver une coloration minimum de G, telle que chaque couleur ne soit pas utilisée plus de k fois. Ce problème est NP-complet pour les graphes d'intervalles. Nous montrons que le MES peut être résolu en temps linéaire pour les graphes d'intervalles propres par un algorithme glouton. La preuve de ce résultat nous fournit aussi un algorithme linéaire en temps pour résoudre le MES pour les graphes d'intervalles sous certaines conditions. Enfin, au travers de cette étude nous obtenons des résultats annexes portant sur la complexité du problème de la coloration uniforme des graphes d'intervalles propres.

Mots clés

"Mutual Exclusion Scheduling", planification d'horaires de travail, graphes d'intervalles propres, colorations, algorithmes linéaires en temps.

Bibtex

@TECHREPORT{02-2002,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{The Mutual Exclusion Scheduling Problem for Proper Interval Graphs}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {02-2002},
    MONTH	= {April},
    YEAR	= {2002},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/02-2002.html},
}