A combinatorial analysis for the critical clause tree

DOI10.1007/S00224-012-9383-6MaRDI QIDQ1946495zbMATH OpenOpenAlexFDO

Authors Masaki Yamamoto

Publication date 15 April 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-012-9383-6

zbMATH Keywords

\(k\)-SATcritical clause tree

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A randomized algorithm for 3-SAT
• A better algorithm for random \(k\)-SAT
• A Better Algorithm for Random k-SAT
• Analyzing Walksat on random formulas
• Why almost all satisfiable k-CNF formulas are easy

Cites work

• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 6469161 (Why is no real title available?)
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• Catalan numbers, their generalization, and their uses
• Solving satisfiability in less than \(2^ n\) steps

Cited in

(1)

• A randomized algorithm for 3-SAT

This page was built for publication: A combinatorial analysis for the critical clause tree

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