New upper bounds for MaxSat

DOI10.1007/3-540-48523-6_54MaRDI QIDQ4938646zbMATH OpenFDO

Authors Rolf Niedermeier, Peter Rossmanith

Publication date 17 October 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48523-6_54

zbMATH Keywords

maximum satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1522934
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• New Upper Bounds for Maximum Satisfiability
• A new upper bound for \(( n , 3)\)-MAX-SAT
• scientific article; zbMATH DE number 2086240

Cited in

(14)

• A refined branching algorithm for the maximum satisfiability problem
• New worst-case upper bounds for SAT
• New upper bounds for the problem of maximal satisfiability
• New Bounds for MAX-SAT by Clause Learning
• New Upper Bounds for Maximum Satisfiability
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• A new algorithm for parameterized MAX-SAT
• Exact algorithms for MAX-SAT
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• Further Reflections on a Theory for Basic Algorithms
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
• MAX SAT approximation beyond the limits of polynomial-time approximation
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Partial minimum satisfiability: fine-grained analysis

This page was built for publication: New upper bounds for MaxSat

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