Improved MaxSAT Algorithms for Instances of Degree 3

DOI10.1007/978-3-319-26626-8_2zbMath1473.68116OpenAlexW2294529032MaRDI QIDQ3467831

Chao Xu, Jianxin Wang, Jian'er Chen

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_2

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete MAXSAT problem
• Linear CNF formulas and satisfiability
• Resolution for Max-SAT
• Improved exact algorithms for MAX-SAT
• A new upper bound for \(( n , 3)\)-MAX-SAT
• Vertex Cover: Further Observations and Further Improvements
• Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• A New Algorithm for Parameterized MAX-SAT
• A Computing Procedure for Quantification Theory
• Theory and Applications of Satisfiability Testing
• On the complexity of \(k\)-SAT

This page was built for publication: Improved MaxSAT Algorithms for Instances of Degree 3