A new algorithm for the propositional satisfiability problem

DOI10.1016/0166-218X(94)00048-IzbMath0836.68080MaRDI QIDQ1894360

Giorgio Gallo, Daniele Pretolani

Publication date: 6 September 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

satisfiabilityenumeration algorithm

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Branching rules for satisfiability, Fuzzy logic programs as hypergraphs. Termination results, On-line algorithms for satisfiability problems with uncertainty, On the complexity of strongly connected components in directed hypergraphs, A linear time algorithm for unique Horn satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The intractability of resolution
• Solving satisfiability in less than \(2^ n\) steps
• Polynomially solvable satisfiability problems
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Branch-and-cut solution of inference problems in propositional logic
• Solving propositional satisfiability problems
• Directed hypergraphs and applications
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Hard examples for resolution
• Algorithms for testing the satisfiability of propositional formulae
• Recognizing disguised NR(1) instances of the satisfiability problem
• `` Strong NP-Completeness Results
• Extended Horn sets in propositional logic
• A Computational Study of Satisfiability Algorithms for Propositional Logic