Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm
Additional Document Info
Springer International Publishing Switzerland 2015. 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 MaxSAT. As a result, we present a parameterized algorithm of time O (1.3248k) for MaxSAT, improving the previous best upper bound O (1.358k) by Bliznets and Golovnev.
name of conference
Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings