Résumé de rapport du LIF

Téléchargement / Download : pdf 160k , ps.gz 196k , bibtex

Abstract

In this paper the problem of the partition of an interval graph into proper interval subgraphs is considered. It arises in a study about the problem of working schedules planning. Here we give some upper bounds on the minimum size of such a partition as well as some efficient algorithms to compute it. In particular, we prove that every K_1,t-free interval graph, t >= 3, is partitionnable into t/2 proper interval subgraphs. The proof of this proposition yields a linear or quasi-linear time algorithm to compute such a partition. Moreover, we give a linear-time algorithm to compute the minimum t such that an interval graph is K_1,t-free. Next, we show that each n-vertex interval graph can be partitionned into O(log n) proper interval subgraphs always in linear or quasi-linear time. Finally, we construct interval graphs for which this bound is sharp.

Keywords

Graph partition, working schedules planning, interval graphs, proper interval graphs, linear-time algorithms.

Résumé

Nous abordons dans cet article le problème de la partition d'un graphe d'intervalles en sous-graphes d'intervalles propres. Celui-ci intervient dans une étude sur la problématique de la planification d'horaires de travail. Nous donnons ici des bornes sur la taille minimum d'une telle partition ainsi que des algorithmes efficaces pour la calculer. En particulier, nous prouvons que tout graphe d'intervalles sans K_1,t , t >= 3, peut être partitionné en t/2 sous-graphes d'intervalles propres. Nous donnons un algorithme linéaire ou quasi-linéaire en temps pour déterminer une telle partition dans la preuve de cette proposition. De plus, nous proposons un algorithme linéaire en temps pour calculer le minimum t pour lequel un graphe d'intervalles est sans K_1,t . Ensuite, nous montrons que tout graphe d'intervalles à n sommets peut être partitionné en O(log n) graphes d'intervalles propres, toujours en un temps linéaire ou quasi-linéaire. Enfin, nous construisons des graphes d'intervalles pour lesquels cette borne est atteinte.

Mots clés

Partition de graphes, planification d'horaires de travail, graphes d'intervalles, graphes d'intervalles propres, algorithmes linéaire en temps.

Bibtex

@TECHREPORT{01-2002,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{On the Partition of an Interval Graph into Proper Interval Subgraphs}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {01-2002},
    MONTH	= {April},
    YEAR	= {2002},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/01-2002.html},
}