Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences

DOI10.1007/978-3-642-02777-2_10zbMath1247.68252OpenAlexW1608133301MaRDI QIDQ3637160

Magnus Wahlström, Daniel Johannsen, Igor Razgon

Publication date: 7 July 2009

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.189.1442

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Algorithmic construction of sets for k -restrictions
• Solving Satisfiability with Less Searching
• An improved exponential-time algorithm for k -SAT
• Algorithms – ESA 2005
• Theory and Applications of Satisfiability Testing
• Unnamed Item

This page was built for publication: Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences