Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms

DOI10.1016/j.tcs.2016.08.008zbMath1423.68476OpenAlexW2489899299MaRDI QIDQ2424882

Chao Xu, Jianxin Wang, Jian'er Chen

Publication date: 25 June 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.08.008

zbMATH Keywords

resolution principleexact algorithmmaximum satisfiabilityparameterized algorithmlinear CNF formula

Mathematics Subject Classification ID

Related Items (1)

Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment

Cites Work

• Unnamed Item
• 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
• Unsatisfiable Linear CNF Formulas Are Large and Complex.
• 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: Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms