How good are branching rules in DPLL?

DOI10.1016/S0166-218X(98)00045-6zbMath0921.68033OpenAlexW1973734335WikidataQ29543496 ScholiaQ29543496MaRDI QIDQ1281405

Ming Ou-Yang

Publication date: 29 September 1999

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00045-6

zbMATH Keywords

satisfiability problemDavis-Putnam-Logemann-Loveland algorithm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the complexity of choosing the branching literal in DPLL, Speeding up Parallel Combinatorial Optimization Algorithms with Las Vegas Method, How important are branching decisions: fooling MIP solvers, Foundations of \(r\)-contiguous matching in negative selection for anomaly detection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Solving propositional satisfiability problems
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• Branching rules for satisfiability
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving