An improved local search algorithm for 3-SAT

Tobias Brueggemann; Walter Kern

doi:10.1016/j.endm.2004.03.021

An improved local search algorithm for 3-SAT

Tobias Brueggemann, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

10 Downloads (Pure)

Abstract

We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο∗ (1.473ⁿ) algorithm for 3-SAT.

Original language	English
Title of host publication	Workshop on Graphs and Combinatorial Optimization (CTW04)
Subtitle of host publication	31 May 2004, Como, Italy
Publisher	Elsevier
Pages	69-73
DOIs	https://doi.org/10.1016/j.endm.2004.03.021
Publication status	Published - 2004
Event	3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004 - Politecnico di Milano, Milano, Italy Duration: 30 May 2004 → 2 Jun 2004 Conference number: 3 http://www.lix.polytechnique.fr/~liberti/ctw04/

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
Volume	17
ISSN (Print)	1571-0653

Workshop

Workshop	3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004
Abbreviated title	CTW
Country/Territory	Italy
City	Milano
Period	30/05/04 → 2/06/04
Internet address	http://www.lix.polytechnique.fr/~liberti/ctw04/

Keywords

Local search
MSC2000: 68Q25
3-SAT
Exact algorithm

Access to Document

10.1016/j.endm.2004.03.021

1 Report

An improved local search algorithm for 3-SAT
Brueggemann, T. & Kern, W., 2004, Enschede: University of Twente. 14 p. (Memorandum; no. 1709)
Research output: Book/Report › Report › Other research output

Open Access
File

Cite this

@inproceedings{a1e0337245ec489881cbf95f86e87510,

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 Ο∗ (1.473n) algorithm for 3-SAT.",

keywords = "Local search, MSC2000: 68Q25, 3-SAT, Exact algorithm",

author = "Tobias Brueggemann and Walter Kern",

year = "2004",

doi = "10.1016/j.endm.2004.03.021",

language = "English",

series = "Electronic Notes in Discrete Mathematics",

publisher = "Elsevier",

pages = "69--73",

booktitle = "Workshop on Graphs and Combinatorial Optimization (CTW04)",

note = "3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004, CTW ; Conference date: 30-05-2004 Through 02-06-2004",

url = "http://www.lix.polytechnique.fr/\textasciitilde{}liberti/ctw04/",

}

Brueggemann, T & Kern, W 2004, An improved local search algorithm for 3-SAT. in Workshop on Graphs and Combinatorial Optimization (CTW04): 31 May 2004, Como, Italy. Electronic Notes in Discrete Mathematics, vol. 17, Elsevier, pp. 69-73, 3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004, Milano, Italy, 30/05/04. https://doi.org/10.1016/j.endm.2004.03.021

TY - GEN

T1 - An improved local search algorithm for 3-SAT

AU - Brueggemann, Tobias

AU - Kern, Walter

N1 - Conference code: 3

PY - 2004

Y1 - 2004

N2 - We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο∗ (1.473n) algorithm for 3-SAT.

AB - We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο∗ (1.473n) algorithm for 3-SAT.

KW - Local search

KW - MSC2000: 68Q25

KW - 3-SAT

KW - Exact algorithm

U2 - 10.1016/j.endm.2004.03.021

DO - 10.1016/j.endm.2004.03.021

M3 - Conference contribution

T3 - Electronic Notes in Discrete Mathematics

SP - 69

EP - 73

BT - Workshop on Graphs and Combinatorial Optimization (CTW04)

PB - Elsevier

T2 - 3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004

Y2 - 30 May 2004 through 2 June 2004

ER -

An improved local search algorithm for 3-SAT

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Research output

An improved local search algorithm for 3-SAT

Cite this