An improved deterministic local search algorithm for 3-SAT

DOI10.1016/j.tcs.2004.08.002zbMath1086.68051OpenAlexW2156223756MaRDI QIDQ706635

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)

Related Items (14)

Parameterized Complexity and Subexponential-Time Computability ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors ⋮ A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ A randomized algorithm for 3-SAT ⋮ Analysis of local search landscapes for \(k\)-SAT instances ⋮ Modelling the dynamics of stochastic local search on \(k\)-SAT ⋮ Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT ⋮ Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Foundations of \(r\)-contiguous matching in negative selection for anomaly detection ⋮ Theoretical advances in artificial immune systems

Cites Work

• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Unnamed Item

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