A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
From MaRDI portal
Publication:3088277
DOI10.1007/978-3-642-22953-4_12zbMath1342.68164arXiv1104.2818OpenAlexW2568591931MaRDI QIDQ3088277
No author found.
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.2818
Related Items (5)
Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Parameterized complexity of MaxSat above average ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
Cites Work
- Unnamed Item
- Unnamed Item
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Complexity of partial satisfaction. II.
- Note on Max Lin-2 above average
- Parameterizing above or below guaranteed values
- Implications of forbidden structures for extremal algorithmic problems
- Solving satisfiability in less than \(2^ n\) steps
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- Kernels: Annotated, Proper and Induced
- Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
- Lower Bounds for Kernelizations and Other Preprocessing Procedures
- Complexity of Partial Satisfaction
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- On the Approximation of Maximum Satisfiability
- On Local Versus Global Satisfiability
This page was built for publication: A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
