A new bound for 3-satisfiable MaxSat and its algorithmic application
From MaRDI portal
Publication:393085
DOI10.1016/j.ic.2013.08.008zbMath1358.68134OpenAlexW2145759487MaRDI QIDQ393085
Publication date: 16 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2013.08.008
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of MaxSat above average
- Solving MAX-\(r\)-SAT above a tight lower bound
- Note on Max Lin-2 above average
- 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.
- Parametrized complexity theory.
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
- 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