Fine-grained parameterized complexity analysis of graph coloring problems

DOI10.1016/j.dam.2022.11.011OpenAlexW2949420075MaRDI QIDQ2112649

Lars Jaffke, Bart M. P. Jansen

Publication date: 11 January 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.11.011

zbMATH Keywords

graph coloringfixed-parameter tractabilitystrong exponential time hypothesisfine-grained complexitystructural parameterizations

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Data reduction for graph coloring problems
• Sparsity. Graphs, structures, and algorithms
• On miniaturized problems in parameterized complexity theory
• Which problems have strongly exponential complexity?
• Parameterized complexity of length-bounded cuts and multicuts
• Parameterized complexity of vertex colouring
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• Set Partitioning via Inclusion-Exclusion
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Fine-grained parameterized complexity analysis of graph coloring problems