A new algorithm for parameterized MAX-SAT

DOI10.1007/978-3-642-33293-7_6MaRDI QIDQ4899239zbMATHOpenAlexFDO

Authors 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

zbMATH Keywords

exact algorithmssatisfiabilityparameterized algorithmsmaximum satisfiability

Mathematics Subject Classification ID

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

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

Cited in

(15)

• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• 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
• A new upper bound for \(( n , 3)\)-MAX-SAT
• Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• A Spectral Method for MAX2SAT in the Planted Solution Model
• An improved branching algorithm for \((n,3)\)-MaxSAT based on refined observations
• On the parameterized complexity of \((k,s)\)-SAT
• Dealing with 4-variables by resolution: an improved MaxSAT algorithm
• A refined branching algorithm for the maximum satisfiability problem

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)