An improved deterministic local search algorithm for 3-SAT

被引：38

作者：

Brueggemann, T ^{[1
]}

Kern, W ^{[1
]}

机构：

[1] Univ Twente, Fac Math Sci, Dept Appl Math, NL-7500 AE Enschede, Netherlands

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 329卷 / 1-3期

关键词：

exact algorithm; local search; 3-SAT;

D O I：

10.1016/j.tcs.2004.08.002

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We slightly improve the pruning technique presented in Dantsin et al. (Theoret. Comput. Sci. 289 (2002) 69) to obtain an O*(1.473(n)) deterministic algorithm for 3-SAT. (C) 2004 Published by Elsevier B.V.

引用

页码：303 / 313

页数：11

共 4 条

[1] A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search [J].

Dantsin, E ;

Goerdt, A ;

Hirsch, EA ;

Kannan, R ;

Kleinberg, J ;

Papadimitriou, C ;

Raghavan, P ;

Schöning, U .

THEORETICAL COMPUTER SCIENCE, 2002, 289 (01) :69-83

[2]

HOFMEISTER T, 2002, LECT NOTES COMPUTER, V2285, P192

[3]

IWAMA K, 2003, LECTURE NOTES SERIES, V53

[4] A Probabilistic algorithm for k-SAT based on limited local search and restart [J].

Schöning, U .

ALGORITHMICA, 2002, 32 (04) :615-623

← 1 →