## 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.*