An improved deterministic local search algorithm for 3-SAT

DOI10.1016/J.TCS.2004.08.002MaRDI QIDQ706635zbMATH OpenOpenAlexFDO

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

(20)

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