An improved local search algorithm for 3-SAT

T. Brueggemann, Walter Kern

Research output: Book/ReportReportOther research output

71 Downloads (Pure)

Abstract

We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an $\mathcal{O}^*\left(1.473^n\right)$ algorithm for 3-SAT.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2004

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1709
ISSN (Print)0169-2690

Keywords

  • MSC-68Q25
  • IR-65894
  • EWI-3529

Cite this

Brueggemann, T., & Kern, W. (2004). An improved local search algorithm for 3-SAT. Enschede: University of Twente, Department of Applied Mathematics.