A space-efficient randomized DNA algorithm for \textit{k}-SAT

DOI10.1007/3-540-44992-2_13MaRDI QIDQ4529982zbMATH OpenFDO

Authors Kevin C. Chen, Vijay Ramachandran

Publication date 7 May 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2054/20540199

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• A DNA-based random walk method for solving k-SAT
• An efficient approach to solving random \(k\)-SAT problems
• A Better Algorithm for Random k-SAT
• A better algorithm for random \(k\)-SAT
• Theory and Applications of Satisfiability Testing
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• An exact and a randomized approach for the satisfiability problem
• Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms.
• Deterministic algorithms for k-SAT based on covering codes and local search

Cited in

(9)

• How efficiently can room at the bottom be traded away for speed at the top?
• Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms.
• Efficient 3-SAT algorithms in the tile assembly model
• How efficiently can room at the bottom be traded away for speed at the top?
• A DNA-based random walk method for solving k-SAT
• A clause string DNA algorithm for SAT
• scientific article; zbMATH DE number 1568795 (Why is no real title available?)
• Solving constraint satisfaction problems with DNA computing
• Theoretical Computer Science

This page was built for publication: A space-efficient randomized DNA algorithm for \textit{k}-SAT

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