Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms

DOI10.1137/0220069MaRDI QIDQ3985811zbMATH OpenOpenAlexFDO

Authors John V. Franco

Publication date 27 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/0002e1de1bc5d35062031f98afca0d7263d628df

zbMATH Keywords

NP-completeprobabilistic analysisresolutionsatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• CNF-Satisfiability Test by Counting and Polynomial Average Time
• On the occurence of null clauses in random instances of Satisfiability
• Theory and Applications of Satisfiability Testing
• Probabilistic performance of a heurisic for the satisfiability problem

Cited in

(9)

• On the occurence of null clauses in random instances of Satisfiability
• A fast parallel SAT-solver -- efficient workload balancing
• The Multi-SAT algorithm
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• Eliminating Redundant Clauses in SAT Instances
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Variable Elimination in Binary CSPs
• Theory and Applications of Satisfiability Testing
• Results related to threshold phenomena research in satisfiability: Lower bounds

This page was built for publication: Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3985811)