Deconstructing Intractability: A Case Study for Interval Constrained Coloring

DOI10.1007/978-3-642-02441-2_19zbMath1247.68196OpenAlexW1531507576MaRDI QIDQ3637114

Christian Komusiewicz, Johannes Uhlmann, Rolf Niedermeier

Publication date: 7 July 2009

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02441-2_19

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

On the approximability of the maximum interval constrained coloring problem ⋮ Approximation algorithms for the interval constrained coloring problem ⋮ The interval constrained 3-coloring problem ⋮ Parameterizing by the number of numbers ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Complexity of Splits Reconstruction for Low-Degree Trees ⋮ Fixed-parameter algorithms for Kemeny rankings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integer Programming with a Fixed Number of Variables
• Approximating the Interval Constrained Coloring Problem
• 3-coloring in time

This page was built for publication: Deconstructing Intractability: A Case Study for Interval Constrained Coloring