Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth

DOI10.4230/LIPIcs.ICALP.2016.28zbMath1388.68128OpenAlexW2550548770MaRDI QIDQ4598164

Dániel Marx, Valia Mitsou

Publication date: 19 December 2017

Full work available at URL: https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#MarxM16

zbMATH Keywords

treewidthparameterized complexitylist coloringlower bounds under ETH

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Unnamed Item ⋮ On some FPT problems without polynomial Turing compressions

This page was built for publication: Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth