An improved local search algorithm for 3-SAT

T. Brueggemann, Walter Kern

Research output: Book/ReportReportOther research output

56 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.
Brueggemann, T. ; Kern, Walter. / An improved local search algorithm for 3-SAT. Enschede : University of Twente, Department of Applied Mathematics, 2004.
@book{dd78685636cb40eb806dca08c9d9f777,
title = "An improved local search algorithm for 3-SAT",
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.",
keywords = "MSC-68Q25, IR-65894, EWI-3529",
author = "T. Brueggemann and Walter Kern",
note = "Imported from MEMORANDA",
year = "2004",
language = "Undefined",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1709",

}

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

An improved local search algorithm for 3-SAT. / Brueggemann, T.; Kern, Walter.

Enschede : University of Twente, Department of Applied Mathematics, 2004.

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - An improved local search algorithm for 3-SAT

AU - Brueggemann, T.

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - MSC-68Q25

KW - IR-65894

KW - EWI-3529

M3 - Report

BT - An improved local search algorithm for 3-SAT

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

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