@article {IOPORT.05883239,
    author       = {Komusiewicz, Christian and Niedermeier, Rolf and Uhlmann, Johannes},
    title        = {Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring.},
    year         = {2011},
    journal      = {Journal of Discrete Algorithms},
    volume       = {9},
    number       = {1},
    issn         = {1570-8667},
    pages        = {137-151},
    publisher    = {Elsevier Science B.V., Amsterdam},
    doi          = {10.1016/j.jda.2010.07.003},
    abstract     = {Summary: The NP-hard Interval Constrained Coloring (ICC) problem appears in the interpretation of experimental data in biochemistry dealing with protein fragments. Given a set of $m$ integer intervals in the range 1 to $n$ and a set of $m$ associated multisets of colors (specifying for each interval the colors to be used for its elements), one asks whether there is a ``consistent'' coloring for all integer points from $\{1,\cdots ,n\}$ that complies with the constraints specified by the color multisets. We thoroughly analyze a known NP-hardness proof for ICC. In this way, we identify numerous parameters that naturally occur in ICC and strongly influence its practical solvability. Accordingly, we present several positive (fixed-parameter) tractability results exploiting various parameterizations. We substantiate the usefulness of this ``multivariate algorithmics approach'' by presenting experimental results with real-world data.},
    identifier   = {05883239},
}