Improved MaxSAT Algorithms for Instances of Degree 3 Conference Paper uri icon

abstract

  • Springer International Publishing Switzerland 2015. The degree of a variable xi in a MaxSAT instance is the number of times xi and xi appearing in the given formula. The degree of a MaxSAT instance is equal to the largest variable degree in the instance. In this paper, we study techniques for solving the MaxSAT problem on instances of degree 3 (briefly, (n, 3)-MaxSAT), which is NP-hard. Two new non-trivial reduction rules are introduced based on the resolution principle. As applications, we present two algorithms for the (n, 3)-MaxSAT problem: a parameterized algorithm of time O(1.194k), and an exact algorithm of time O(1.237n), improving the previous best upper bounds O(1.2721k) and O(1.2600n), respectively.

name of conference

  • Combinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings

published proceedings

  • COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015)

author list (cited authors)

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

citation count

  • 0

complete list of authors

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

publication date

  • December 2015