Fixed-parameter tractable reductions to SAT

DOI10.1007/978-3-319-09284-3_8MaRDI QIDQ3192057zbMATH OpenOpenAlexFDO

Authors Ronald de Haan, Stefan Szeider

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09284-3_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Parameterized complexity classes beyond para-NP
• Theory and Applications of Satisfiability Testing
• SAT-Problems and Reductions with Respect to the Number of Variables
• scientific article; zbMATH DE number 6297727
• Theory and Applications of Satisfiability Testing

Cited in

(15)

• Almost 2-SAT is fixed-parameter tractable
• Recognition of tractable satisfiability problems through balanced polynomial representations
• Parameterized complexity classes beyond para-NP
• On the query complexity of selecting minimal sets for monotone predicates
• Strong Backdoors for Default Logic
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• SAT-Problems and Reductions with Respect to the Number of Variables
• Treewidth with a quantifier alternation revisited
• Backdoors to normality for disjunctive logic programs
• Experiments with reduction finding
• Strong backdoors for default logic
• Strong backdoors for default logic
• On kernelization with access to NP-oracles
• Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

This page was built for publication: Fixed-parameter tractable reductions to SAT

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