A simplified NP-complete MAXSAT problem

DOI10.1016/S0020-0190(97)00223-8MaRDI QIDQ293164zbMATHOpenAlexFDO

Authors Venkatesh Raman, S. Srinivasa Rao, B. Ravikumar

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097002238?np=y

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A simplified NP-complete satisfiability problem
• Exact algorithms for MAX-SAT
• A new upper bound for \(( n , 3)\)-MAX-SAT
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

Cites work

• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• A simplified NP-complete satisfiability problem
• On the complexity of the maximum satisfiability problem for Horn formulas
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Solving satisfiability in less than \(2^ n\) steps
• Some simplified NP-complete graph problems
• The Euclidean traveling salesman problem is NP-complete
• The Minimum Satisfiability Problem
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(25)

• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• Max NP-completeness made easy
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• On star partition of split graphs
• An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
• Optimal 2-constraint satisfaction via sum-product algorithms
• The maximum 3-star packing problem in claw-free cubic graphs
• A new upper bound for \(( n , 3)\)-MAX-SAT
• Drawing (complete) binary tanglegrams
• Network design with a discrete set of traffic matrices
• Gene tree reconciliation including transfers with replacement is NP-hard and FPT
• A new algorithm for optimal 2-constraint satisfaction and its implications
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• About a surprising computer program of Matthias Müller
• Learning hierarchical probabilistic logic programs
• A simplified NP-complete satisfiability problem
• A refined branching algorithm for the maximum satisfiability problem
• The inequality-satisfiability problem
• Popular spanning trees
• Complexity of partial satisfaction. II.
• Directed molecular evolution by machine learning and the influence of nonlinear interactions
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

This page was built for publication: A simplified NP-complete MAXSAT problem

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