Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring

DOI10.1016/j.jda.2010.07.003zbMath1228.05154OpenAlexW2147091866MaRDI QIDQ533417

Johannes Uhlmann, Christian Komusiewicz, Rolf Niedermeier

Publication date: 3 May 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.07.003

zbMATH Keywords

experimentsNP-hard problemparametrized complexityinterval constraint coloringmultivariate algorithmics

Mathematics Subject Classification ID

Applications of graph theory (05C90) Coloring of graphs and hypergraphs (05C15)

Related Items

Studies in Computational Aspects of Voting, Bivariate Complexity Analysis of Almost Forest Deletion, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Aspects of a multivariate complexity analysis for rectangle tiling, The effect of homogeneity on the computational complexity of combinatorial data anonymization, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Exploiting a hypergraph model for finding Golomb rulers, Complexity of splits reconstruction for low-degree trees, Parameterizing by the number of numbers, NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, The Effect of Homogeneity on the Complexity of k-Anonymity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An application of simultaneous diophantine approximation in combinatorial optimization
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Approximating the Interval Constrained Coloring Problem
• The Interval Constrained 3-Coloring Problem
• Graph Layout Problems Parameterized by Vertex Cover
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Kernelization: New Upper and Lower Bound Techniques
• 3-coloring in time
• A Polynomial Delay Algorithm for Enumerating Approximate Solutions to the Interval Constrained Coloring Problem