A simplified NP-complete MAXSAT problem
From MaRDI portal
Publication:293164
DOI10.1016/S0020-0190(97)00223-8zbMath1339.68122OpenAlexW2052367117MaRDI QIDQ293164
S. Srinivasa Rao, Venkatesh Raman, Bala 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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (17)
Optimal 2-constraint satisfaction via sum-product algorithms ⋮ Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ On the computational complexity of Roman\(\{2\}\)-domination in grid graphs ⋮ Directed molecular evolution by machine learning and the influence of nonlinear interactions ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ Drawing (complete) binary tanglegrams ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ A new upper bound for \(( n , 3)\)-MAX-SAT ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Network design with a discrete set of traffic matrices ⋮ POPULAR SPANNING TREES ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Learning hierarchical probabilistic logic programs ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ A refined branching algorithm for the maximum satisfiability problem
Cites Work
- Unnamed Item
- A simplified NP-complete satisfiability problem
- Solving satisfiability in less than \(2^ n\) steps
- On the complexity of the maximum satisfiability problem for Horn formulas
- Some simplified NP-complete graph problems
- The Euclidean traveling salesman problem is NP-complete
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Two-Processor Scheduling with Start-Times and Deadlines
- The Minimum Satisfiability Problem
This page was built for publication: A simplified NP-complete MAXSAT problem