Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
From MaRDI portal
Publication:2283027
DOI10.1016/j.tcs.2019.11.033zbMath1436.68216OpenAlexW2989778209WikidataQ126647435 ScholiaQ126647435MaRDI QIDQ2283027
Ivan A. Bliznets, Tatiana Belova
Publication date: 27 December 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.11.033
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- A simplified NP-complete MAXSAT problem
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Fixed-parameter tractability of satisfying beyond the number of variables
- Vertex cover problem parameterized above and below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable
- An improved branching algorithm for \((n,3)\)-MaxSAT based on refined observations
- Improved exact algorithms for MAX-SAT
- A new upper bound for \(( n , 3)\)-MAX-SAT
- Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
- The linear arrangement problem parameterized above guaranteed value
- New upper bounds for the problem of maximal satisfiability
- Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm
- A new approach to proving upper bounds for MAX-2-SAT
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- New Upper Bounds for Maximum Satisfiability
- A New Algorithm for Parameterized MAX-SAT
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Algorithmic aspects in speech recognition
- Partially Polynomial Kernels for Set Cover and Test Cover
