A polynomial-time algorithm for reducing the number of variables in MAX SAT problem

DOI10.1007/BF02916605zbMath0881.68086OpenAlexW2078775294MaRDI QIDQ1367267

Shaohan Ma, Dongmin Liang

Publication date: 21 September 1997

Published in: Science in China. Series E (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02916605

zbMATH Keywords

maximum satisfiabilityMAX SAT problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (max. 100)

Irreducible subcube partitions ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ On semidefinite least squares and minimal unsatisfiability ⋮ Investigations on autark assignments

Cites Work

• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial-time algorithm for reducing the number of variables in MAX SAT problem