Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting

DOI10.3233/FI-2015-1159zbMATH Open1337.68127OpenAlexW1767868015MaRDI QIDQ2805407FDOQ2805407

Nadia Creignou, Heribert Vollmer

Publication date: 11 May 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2015-1159

zbMATH Keywords

Boolean functionparametrized complexityBoolean circuitweighted satisfiabilityPost latticeparametrized counting complexitypolynomial-delay enumeration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (5)

• Succinct monotone circuit certification: planarity and parameterized complexity
• Succinct certification of monotone circuits
• A complexity theory for hard enumeration problems
• Enumerating teams in first-order team logics
• Weighted NP Optimization Problems: Logical Definability and Approximation Properties

This page was built for publication: Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805407)