On Variables with Few Occurrences in Conjunctive Normal Forms
From MaRDI portal
Publication:3007672
DOI10.1007/978-3-642-21581-0_5zbMath1331.68110arXiv1010.5756MaRDI QIDQ3007672
Publication date: 17 June 2011
Published in: Theory and Applications of Satisfiability Testing - SAT 2011 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.5756
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
03B05: Classical propositional logic
Related Items
On Davis-Putnam reductions for minimally unsatisfiable clause-sets, On Variables with Few Occurrences in Conjunctive Normal Forms, Computing Maximal Autarkies with Few and Simple Oracle Queries
Cites Work
- A simplified NP-complete satisfiability problem
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- On subclasses of minimal unsatisfiable formulas
- Two tractable subclasses of minimal unsatisfiable formulas
- Constraint Satisfaction Problems in Clausal Form I: Autarkies and Deficiency
- On Variables with Few Occurrences in Conjunctive Normal Forms
- Green-Tao Numbers and SAT