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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349213
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 27 juillet 2016 - 08:19:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

interval-scheduling-and-colorf...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

200