A new algorithm for parameterized MAX-SAT

DOI10.1007/978-3-642-33293-7_6MaRDI QIDQ4899239zbMATH OpenOpenAlexFDO

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)

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