An efficient algorithm for the 3-satisfiability problem

DOI10.1016/0167-6377(92)90019-YzbMath0757.90059OpenAlexW2067478703MaRDI QIDQ1200758

Alain Sutter, Alain Billionnet

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90019-y

zbMATH Keywords

satisfiability problemconcensusDavis and Putnam scheme

Mathematics Subject Classification ID

Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Unnamed Item, Another look at graph coloring via propositional satisfiability, Toward leaner binary-clause reasoning in a satisfiability solver

Cites Work

• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• Some results and experiments in programming techniques for propositional logic
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Solving Satisfiability with Less Searching
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Algorithms for testing the satisfiability of propositional formulae
• On the Complexity of Timetable and Multicommodity Flow Problems
• A Computing Procedure for Quantification Theory
• The Problem of Simplifying Truth Functions