RenĂ© van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), Taipei, Taiwan, volume 7676 of Lecture Notes in Computer Science, pages 247–256. Springer, 2012. The final version of this article appeared in Journal of Scheduling.

The NP-hard Independent Set problem is to determine for a 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 encounters 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 preprocessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.

bib | DOI | journal version ] Back


This file was generated by bibtex2html 1.98.