Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
From MaRDI portal
Publication:414863
Recommendations
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Parameterized constraint satisfaction problems: a survey
- Improved parameterized algorithms for above average constraint satisfaction
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
Cites work
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Geometric Approach to Betweenness
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A new approach to cyclic ordering of 2D orientations using ternary relation algebras
- A probabilistic approach to problems parameterized above or below tight bounds
- Betweenness parameterized above tight lower bound
- Cyclic ordering is NP-complete
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter complexity of minimum profile problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Interval Completion Is Fixed Parameter Tractable
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernelization: new upper and lower bound techniques
- Logarithmic Sobolev Inequalities
- Note on Max Lin-2 above average
- On Random Betweenness Constraints
- On Random Ordering Constraints
- On problems without polynomial kernels
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Parametrized complexity theory.
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- The linear arrangement problem parameterized above guaranteed value
- Total Ordering Problem
- Vertex cover problem parameterized above and below tight bounds
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(17)- Detours in directed graphs
- Confronting intractability via parameters
- Parameterized constraint satisfaction problems: a survey
- scientific article; zbMATH DE number 7525484 (Why is no real title available?)
- Betweenness parameterized above tight lower bound
- Turán’s Theorem Through Algorithmic Lens
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Large independent sets in subquartic planar graphs
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Finding detours is fixed-parameter tractable
- Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Linear kernels and linear-time algorithms for finding large cuts
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Going far from degeneracy
- Large independent sets in triangle-free planar graphs
- Approximating long cycle above Dirac's guarantee
This page was built for publication: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414863)
