Parameterized constraint satisfaction problems: a survey
From MaRDI portal
Recommendations
Cites work
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- A Geometric Approach to Betweenness
- A new approach to cyclic ordering of 2D orientations using ternary relation algebras
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A probabilistic approach to problems parameterized above or below tight bounds
- Algorithms with large domination ratio
- Almost 2-SAT is fixed-parameter tractable
- Analysis of Boolean Functions
- Beating the random ordering is hard: every ordering CSP is approximation resistant
- Betweenness parameterized above tight lower bound
- Complexity of Partial Satisfaction
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3902051 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1324671 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Improved parameterized algorithms for above average constraint satisfaction
- Kernel bounds for disjoint cycles and disjoint paths
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Note on maximal bisection above tight lower bound
- On fixed-parameter tractability and approximability of NP optimization problems
- On problems without polynomial kernels
- On the Approximation of Maximum Satisfiability
- On the power of unique 2-prover 1-round games
- Parameterized algorithms
- Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Paths, flowers and vertex cover
- Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Solving MAX-\(r\)-SAT above a tight lower bound
- Some optimal inapproximability results
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Total Ordering Problem
- Voting paradoxes and digraphs realizations
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(15)- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Improved parameterized algorithms for above average constraint satisfaction
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Constraint Satisfaction Parameterized by Solution Size
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
- A new approach to partial constraint satisfaction problems
- Optimal polynomial-time compression for Boolean Max CSP
- Parameterized complexity and kernelizability of max ones and exact ones problems
- Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
- Note on Max Lin-2 above average
- Optimal polynomial-time compression for Boolean Max CSP
- A fast algorithm for maximum satisfiability above half number of clauses
This page was built for publication: Parameterized constraint satisfaction problems: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993600)
