Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm Conference Paper uri icon


  • 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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Chen, J., Xu, C., & Wang, J.

citation count

  • 6

complete list of authors

  • Chen, Jianer||Xu, Chao||Wang, Jianxin

publication date

  • January 2015