Parameterized complexity of constraint satisfaction problems

DOI10.1007/s00037-005-0195-9zbMath1085.68068OpenAlexW2107918022MaRDI QIDQ814421

Dániel Marx

Publication date: 7 February 2006

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0195-9

zbMATH Keywords

parameterized complexityweak separabilityConstraint satisfactionweighted satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Tractability in constraint satisfaction problems: a survey ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Solving linear equations parameterized by Hamming weight ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Parameterized random complexity ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Constraint Satisfaction Parameterized by Solution Size ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

This page was built for publication: Parameterized complexity of constraint satisfaction problems