An improved local search algorithm for 3-SAT

T. Brueggemann, W. Kern

Research output: Book/ReportReportOther research output

69 Downloads (Pure)

Abstract

We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο* (1.473n) algorithm for 3-SAT.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages14
Publication statusPublished - 2004

Publication series

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

Keywords

  • MSC-68Q25
  • Exact algorithm
  • Local search
  • 3-SAT

Fingerprint Dive into the research topics of 'An improved local search algorithm for 3-SAT'. Together they form a unique fingerprint.

Cite this