An improved local search algorithm for 3-SAT

T. Brueggemann, W. Kern

Research output: Book/Report › Report › Other research output

1 Citation (Scopus)
199 Downloads (Pure)

Abstract

We slightly improve the pruning technique presented in Dantsin et. al. (2002) to obtain an Ο* (1.473n) algorithm for 3-SAT.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages14
Publication statusPublished - 2004

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1709
ISSN (Print)0169-2690

Keywords

  • MSC-68Q25
  • Exact algorithm
  • Local search
  • 3-SAT

Access to Document

    Fingerprint

    Dive into the research topics of 'An improved local search algorithm for 3-SAT'. Together they form a unique fingerprint.
    View full fingerprint
    • 1 Citations
    • 1 Conference contribution

    • An improved local search algorithm for 3-SAT

      Brueggemann, T. & Kern, W., 2004, Workshop on Graphs and Combinatorial Optimization (CTW04): 31 May 2004, Como, Italy. Elsevier, p. 69-73 (Electronic Notes in Discrete Mathematics; vol. 17).

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

      10 Downloads (Pure)

    Cite this