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

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

zbMATH Keywords

3-SATLocal searchExact algorithm

Mathematics Subject Classification ID

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

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.
• Title not available (Why is that?)

Cited In (19)

• An improved local search algorithm for 3-SAT
• Parameterized Complexity and Subexponential-Time Computability
• Algorithms and Computation
• Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Theoretical advances in artificial immune systems
• Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
• 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
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Derandomizing the HSSW algorithm for 3-SAT
• Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
• Solving connected dominating set faster than \(2^n\)
• 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)