An improved deterministic local search algorithm for 3-SAT

DOI10.1016/J.TCS.2004.08.002zbMATH Open1086.68051OpenAlexW2156223756MaRDI QIDQ706635FDOQ706635

Authors Tobias Brueggemann, Walter Kern

Publication date 9 February 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.08.002

zbMATH Keywords

3-SATLocal searchExact algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• scientific article; zbMATH DE number 1670827
• Guided Search and a Faster Deterministic Algorithm for 3-SAT
• Algorithms and Computation
• scientific article; zbMATH DE number 2086385

Cites work

• scientific article; zbMATH DE number 2086385 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart

Cited in

(19)

• Modelling the dynamics of stochastic local search on \(k\)-SAT
• Analysis of local search landscapes for \(k\)-SAT instances
• Guided Search and a Faster Deterministic Algorithm for 3-SAT
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions
• Algorithms and Computation
• A randomized algorithm for 3-SAT
• Improved polynomial algorithm for 3-SAT
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Solving connected dominating set faster than \(2^n\)
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized complexity and subexponential-time computability
• An improved local search algorithm for 3-SAT
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Theoretical advances in artificial immune systems
• Foundations of \(r\)-contiguous matching in negative selection for anomaly detection
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors

This page was built for publication: An improved deterministic local search algorithm for 3-SAT

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