## Matthias Bentert, René van Bevern, and Rolf Niedermeier.
Inductive *k*-independent graphs and *c*-colorable subgraphs in
scheduling: A review.
*Journal of Scheduling*, 2018.
In press.

Inductive k-independent graphs generalize chordal
graphs and have recently been advocated in the
context of interference-avoiding wireless
communication scheduling. The NP-hard problem of
finding maximum-weight induced c-colorable
subgraphs, which is a generalization of finding
maximum independent sets, naturally occurs when
selecting c sets of pairwise non-conflicting jobs
(modeled as graph vertices). We investigate the
parameterized complexity of this problem on
inductive k-independent graphs. We show that the
Independent Set problem is W[1]-hard even on
2-simplicial 3-minoes—a subclass of inductive
2-independent graphs. In contrast, we prove that the
more general Maximum c-Colorable Subgraph problem is
fixed-parameter tractable on edge-wise unions of
cluster and chordal graphs, which are
2-simplicial. In both cases, the parameter is the
solution size. Aside from this, we survey other
graph classes between inductive 1-inductive and
inductive 2-inductive graphs with applications in
scheduling.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*