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

abstract

• 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

authors

• Chen, Jianer

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

publisher

• Springer Nature  Publisher

published in

• n1611-3349ISSN  Journal

keywords

• 46 Information And Computing Sciences
• 4602 Artificial Intelligence
• Bioengineering

Digital Object Identifier (DOI)

• 10.1007/978-3-319-21840-3_15

International Standard Book Number (ISBN) 13

• 9783319218397

start page

• 178

end page

• 188

volume

• 9214

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-3-319-21840-3_15