A refined branching algorithm for the maximum satisfiability problem
From MaRDI portal
Publication:2118385
DOI10.1007/S00453-022-00938-8OpenAlexW4210922699MaRDI QIDQ2118385FDOQ2118385
Authors: Wen-Jun Li, Chao Xu, Yongjie Yang, Jianxin Wang, Jianer Chen 
Publication date: 22 March 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-00938-8
Recommendations
- An improved branching algorithm for \((n,3)\)-MaxSAT based on refined observations
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Exact algorithms for MAX-SAT
- Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
- scientific article; zbMATH DE number 2086240
Cites Work
- CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exact exponential algorithms.
- The complexity of satisfiability problems
- On the complexity of \(k\)-SAT
- Some simplified NP-complete graph problems
- Iterative and core-guided maxsat solving: a survey and assessment
- Improved upper bounds for vertex cover
- A simplified NP-complete MAXSAT problem
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- The nature of computation
- New inference rules for Max-SAT
- Approximating satisfiable satisfiability problems
- Kernelization: new upper and lower bound techniques
- New Bounds for MAX-SAT by Clause Learning
- New Upper Bounds for Maximum Satisfiability
- Title not available (Why is that?)
- Improved exact algorithms for MAX-SAT
- Scoring functions based on second level score for \(k\)-SAT with long clauses
- The configurable SAT solver challenge (CSSC)
- A new algorithm for parameterized MAX-SAT
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- Title not available (Why is that?)
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- A new upper bound for \(( n , 3)\)-MAX-SAT
Cited In (7)
- Branching constraint satisfaction problems and Markov decision problems compared
- Targeted Branching for the Maximum Independent Set Problem
- Recent Advances in Constraints
- Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
- New updating criteria for conflict-based branching heuristics in DPLL algorithms for satisfiability
- Generalization of the subset sum problem and cubic forms
- Using the method of conditional expectations to supply an improved starting point for CCLS
Uses Software
This page was built for publication: A refined branching algorithm for the maximum satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118385)
