Résumé de rapport du LIF

Téléchargement / Download : pdf 152k , ps.gz 184k , bibtex

Abstract

In this paper we consider the problem of determining a maximum matching in a set of intervals (two intervals can be matched if they are disjoint). We propose an incremental algorithm to compute such a maximum disjoint matching. We show that this algorithm runs in O(n) time if the list of sorted endpoints of the set of intervals is given in input. This result is applied to solve efficiently particular cases of two scheduling problems: working schedules planning and mutual exclusion scheduling for interval graphs.

Keywords

Matchings, interval graphs, linear-time algorithms, working schedules planning, mutual exclusion scheduling.

Résumé

Dans ce papier, nous considérons le problème de la détermination du couplage maximum dans un ensemble d'intervalles (deux intervalles pouvent être couplés s'ils sont disjoints). Nous proposons un algorithme incrémental pour calculer un tel couplage. Nous montrons que cet algoritme s'exécute en O(n) si la liste des extrémités triées de l'ensemble des intervalles est donnée en entrée. Ce résultat est appliqué à la résolution de cas particuliers de deux problèmes de "scheduling" : la planification d'horaires de travail et le "mutual exclusion scheduling " pour les graphes d'intervalles.

Mots clés

Couplages, graphes d'intervalles, algorithmes linéaire en temps, planification d'horaires de travail, "mutual exclusion scheduling".

Bibtex

@TECHREPORT{07-2002,
    AUTHOR	= {Frédéric Gardi},
    TITLE	= {{An efficient algorithm for maximum disjoint matchings in a set of intervals and related problems}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {07-2002},
    MONTH	= {May},
    YEAR	= {2002},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/07-2002.html},
}