A new bound for 3-satisfiable MaxSat and its algorithmic application
From MaRDI portal
Publication:393085
DOI10.1016/J.IC.2013.08.008zbMATH Open1358.68134OpenAlexW2145759487MaRDI QIDQ393085FDOQ393085
G. Gutin, D. Scheder, A. Yeo, M. Jones
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
Recommendations
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- A new algorithm for parameterized MAX-SAT
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
Cites Work
- Kernels: Annotated, Proper and Induced
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Parametrized complexity theory.
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Solving MAX-\(r\)-SAT above a tight lower bound
- Title not available (Why is that?)
- Solving satisfiability in less than \(2^ n\) steps
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- Implications of forbidden structures for extremal algorithmic problems
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- 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
- A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
- 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
- Parameterized complexity of MaxSat above average
- On the Approximation of Maximum Satisfiability
- On Local Versus Global Satisfiability
- Title not available (Why is that?)
- Note on Max Lin-2 above average
Cited In (10)
- New methods for 3-SAT decision and worst-case analysis
- Title not available (Why is that?)
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Conditional Hardness of Approximating Satisfiable Max 3CSP-q
- The Approximability of Three-valued MAX CSP
- On the parallel parameterized complexity of MaxSAT variants
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Title not available (Why is that?)
- A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
This page was built for publication: A new bound for 3-satisfiable MaxSat and its algorithmic application
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393085)
