Solving MAX-r-SAT above a tight lower bound
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3141016 (Why is no real title available?)
- scientific article; zbMATH DE number 3495588 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 5485570 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A probabilistic approach to problems parameterized above or below tight bounds
- Algorithms with large domination ratio
- Betweenness parameterized above tight lower bound
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- Fixed-parameter complexity of minimum profile problems
- Graph theory
- Improving exact algorithms for MAX-2-SAT
- Interval Completion Is Fixed Parameter Tractable
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernelization: new upper and lower bound techniques
- On problems without polynomial kernels
- On the advantage over a random assignment
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Some optimal inapproximability results
- Some simplified NP-complete graph problems
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- The linear arrangement problem parameterized above guaranteed value
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(42)- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Long directed detours: reduction to 2-disjoint paths
- Parameterizations of test cover with bounded test sizes
- Parameterized algorithms for finding square roots
- Solving #SAT and MAXSAT by Dynamic Programming
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- scientific article; zbMATH DE number 7651202 (Why is no real title available?)
- A complete parameterized complexity analysis of bounded planning
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Parameterized traveling salesman problem: beating the average
- Linear kernels and linear-time algorithms for finding large cuts
- Improved parameterized algorithms for above average constraint satisfaction
- Basic Terminology, Notation and Results
- On the parallel parameterized complexity of MaxSAT variants
- Parameterized pre-coloring extension and list coloring problems
- Faster existential FO model checking on posets
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Domination above \(r\)-independence: does sparseness help?
- Parameterized aspects of strong subgraph closure
- The complexity of degree anonymization by vertex addition
- Alternative parameterizations of \textsc{Metric Dimension}
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Meta-kernelization using well-structured modulators
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Finding detours is fixed-parameter tractable
- Parameterized aspects of strong subgraph closure
- A completeness theory for polynomial (Turing) kernelization
- Turán’s Theorem Through Algorithmic Lens
- Large independent sets in triangle-free planar graphs
- On some FPT problems without polynomial Turing compressions
- Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
- Simultaneous approximation of constraint satisfaction problems
- Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
- Parameterized complexity and kernelizability of max ones and exact ones problems
- Parameterized constraint satisfaction problems: a survey
- Fixed-parameter tractability of satisfying beyond the number of variables
This page was built for publication: Solving MAX-\(r\)-SAT above a tight lower bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644808)
