A new algorithm for parameterized MAX-SAT

DOI10.1007/978-3-642-33293-7_6zbMATH Open1360.68494OpenAlexW34340600MaRDI QIDQ4899239FDOQ4899239

Alexander Golovnev, I. A. Bliznets

Publication date: 7 January 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-33293-7_6

Recommendations

• scientific article; zbMATH DE number 2086240
• Improved exact algorithms for MAX-SAT
• scientific article; zbMATH DE number 1522934
• Publication:4938646
• A new bound for 3-satisfiable MaxSat and its algorithmic application

zbMATH Keywords

exact algorithmssatisfiabilityparameterized algorithmsmaximum satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cited In (9)

• A Spectral Method for MAX2SAT in the Planted Solution Model
• A refined branching algorithm for the maximum satisfiability problem
• Improved MaxSAT Algorithms for Instances of Degree 3
• An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• Dealing with 4-variables by resolution: an improved MaxSAT algorithm
• Improved exact algorithms for mildly sparse instances of MAX SAT

This page was built for publication: A new algorithm for parameterized MAX-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899239)