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

DOI10.3233/FI-2015-1159MaRDI QIDQ2805407zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Parameterized complexity of weighted satisfiability problems
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Parameterized complexity of constraint satisfaction problems
• When is weighted satisfiability FPT?
• The Complexity of Weighted Boolean #CSP

Cited in

(15)

• Parameterized and subexponential-time complexity of satisfiability problems and applications
• W-hierarchies defined by symmetric gates
• Completely inapproximable monotone and antimonotone parameterized problems
• Parameterized complexity of constraint satisfaction problems
• Succinct monotone circuit certification: planarity and parameterized complexity
• Paradigms for parameterized enumeration
• When is weighted satisfiability FPT?
• Succinct certification of monotone circuits
• Parameterized complexity of weighted satisfiability problems
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Enumerating teams in first-order team logics
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Weighted NP Optimization Problems: Logical Definability and Approximation Properties
• The weight in enumeration

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)