An improved local search algorithm for 3-SAT

Tobias Brueggemann, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο∗ (1.473n) algorithm for 3-SAT.
Original languageEnglish
Title of host publicationWorkshop on Graphs and Combinatorial Optimization (CTW04)
Subtitle of host publication31 May 2004, Como, Italy
PublisherElsevier
Pages69-73
DOIs
Publication statusPublished - 2004
Event3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004 - Politecnico di Milano, Milano, Italy
Duration: 30 May 20042 Jun 2004
Conference number: 3
http://www.lix.polytechnique.fr/~liberti/ctw04/

Publication series

NameElectronic Notes in Discrete Mathematics
PublisherElsevier
Volume17
ISSN (Print)1571-0653

Workshop

Workshop3rd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2004
Abbreviated titleCTW
CountryItaly
CityMilano
Period30/05/042/06/04
Internet address

Keywords

  • Local search
  • MSC2000: 68Q25
  • 3-SAT
  • Exact algorithm

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

Cite this