A SIMPLIFIED NP-COMPLETE MAXSAT PROBLEM

Authors
RAMAN V RAVIKUMAR B RAO SS
Citation
V. Raman et al., A SIMPLIFIED NP-COMPLETE MAXSAT PROBLEM, Information processing letters, 65(1), 1998, pp. 1-6
Citations number
10
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
1
Year of publication
1998
Pages
1 - 6
Database
ISI
SICI code
0020-0190(1998)65:1<1:ASNMP>2.0.ZU;2-4
Abstract
It is shown that the MAX2SAT problem is NP-complete even if every vari able appears in at most three clauses. However, if every variable appe ars in at most two clauses, it is shown that it (and even the general MAXSAT problem) can be solved in linear time. When every variable appe ars in at most three clauses, we give an exact algorithm for MAXSAT th at takes at most 0(3(n/2)n) steps where n is the number of variables. (C) 1998 Published by Elsevier Science B.V.