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 circuitBoolean functionparametrized complexityparametrized counting complexitypolynomial-delay enumerationPost latticeweighted satisfiability

Mathematics Subject Classification ID

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

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)

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

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)