Interval scheduling and colorful independent sets

Abstract : TheNP-hardIndependentSetproblemistodeterminefora given graph G and an integer k whether G contains a set of k pairwise non- adjacent vertices. The problem has numerous applications in scheduling, including resource allocation and steel manufacturing. There, one encoun- ters restricted graph classes such as 2-union graphs, which are edge-wise unions of two interval graphs on the same vertex set, or strip graphs, where additionally one of the two interval graphs is a disjoint union of cliques. We prove NP-hardness of Independent Set on a very restricted subclass of 2-union graphs and identify natural parameterizations to chart the possibilities and limitations of effective polynomial-time prepro- cessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2015, 18 (5), pp.449-469. 〈10.1007/s10951-014-0398-5〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 27 juillet 2016 - 08:19:18
Dernière modification le : mercredi 10 octobre 2018 - 14:28:13


Fichiers produits par l'(les) auteur(s)




René Van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, Springer Verlag, 2015, 18 (5), pp.449-469. 〈10.1007/s10951-014-0398-5〉. 〈lirmm-01349213〉



Consultations de la notice


Téléchargements de fichiers