Parameterized complexity of weighted satisfiability problems

DOI10.1007/978-3-642-31612-8_26MaRDI QIDQ2843338zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Heribert Vollmer

Publication date 12 August 2013

Published in Theory and Applications of Satisfiability Testing – SAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31612-8_26

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: decision, enumeration, counting
• Mathematical Foundations of Computer Science 2005
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Parameterized complexity of constraint satisfaction problems
• When is weighted satisfiability FPT?

Cited in

(16)

• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Completely inapproximable monotone and antimonotone parameterized problems
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Uniform CSP parameterized by solution size is in W[1]
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• When is weighted satisfiability FPT?
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• A Purely Democratic Characterization of W[1]
• Weighted NP Optimization Problems: Logical Definability and Approximation Properties
• Parameterized Weighted Containment
• Mathematical Foundations of Computer Science 2005
• 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

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