An improved deterministic local search algorithm for 3-SAT

T. Brueggemann; Walter Kern

doi:10.1016/j.tcs.2004.08.002

An improved deterministic local search algorithm for 3-SAT

T. Brueggemann, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

62 Citations (Scopus)

12 Downloads (Pure)

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 language	Undefined
Pages (from-to)	303-313
Number of pages	10
Journal	Theoretical computer science
Volume	329
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2004.08.002
Publication status	Published - 2004

Keywords

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

Access to Document

10.1016/j.tcs.2004.08.002

Cite this

@article{f3f939c1d02841e9b7d0da303a666121,

title = "An improved deterministic local search algorithm for 3-SAT",

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.",

keywords = "Local search, 3-SAT, IR-76360, Exact algorithm, METIS-219386",

author = "T. Brueggemann and Walter Kern",

year = "2004",

doi = "10.1016/j.tcs.2004.08.002",

language = "Undefined",

volume = "329",

pages = "303--313",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - An improved deterministic local search algorithm for 3-SAT

AU - Brueggemann, T.

AU - Kern, Walter

PY - 2004

Y1 - 2004

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

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

KW - Local search

KW - 3-SAT

KW - IR-76360

KW - Exact algorithm

KW - METIS-219386

U2 - 10.1016/j.tcs.2004.08.002

DO - 10.1016/j.tcs.2004.08.002

M3 - Article

SN - 0304-3975

VL - 329

SP - 303

EP - 313

JO - Theoretical computer science

JF - Theoretical computer science

IS - 1-3

ER -