| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4952187 | Theoretical Computer Science | 2017 | 12 Pages |
Abstract
We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time Oâ(1.3248k) for the MaxSAT problem, improving the previous best upper bound Oâ(1.358k) by Ivan Bliznets and Alexander Golovnev.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jianer Chen, Chao Xu, Jianxin Wang,