Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms

DOI10.1137/0220069zbMath0738.68041OpenAlexW2076342862MaRDI QIDQ3985811

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

probabilistic analysisNP-completeresolutionsatisfiability

Mathematics Subject Classification ID

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

Related Items (6)

A fast parallel SAT-solver -- efficient workload balancing ⋮ On Davis-Putnam reductions for minimally unsatisfiable clause-sets ⋮ The \(Multi\)-SAT algorithm ⋮ On the occurence of null clauses in random instances of Satisfiability ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon

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