An improved deterministic local search algorithm for 3-SAT

T. Brueggemann, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

53 Citations (Scopus)

Abstract

We slightly improve the pruning technique presented in Dantsin et al. (Theoret. Comput. Sci. 289 (2002) 69) to obtain an O*(1.473n) deterministic algorithm for 3-SAT.
Original languageUndefined
Pages (from-to)303-313
Number of pages10
JournalTheoretical computer science
Volume329
Issue number1-3
DOIs
Publication statusPublished - 2004

Keywords

  • Local search
  • 3-SAT
  • IR-76360
  • Exact algorithm
  • METIS-219386

Cite this