Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
DOI10.1016/J.JCSS.2011.01.004zbMATH Open1242.68122OpenAlexW2161806016MaRDI QIDQ414863FDOQ414863
Authors: G. Gutin, Matthias Mnich, A. Yeo, Leo Van Iersel 
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.01.004
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
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- Betweenness parameterized above tight lower bound
- Parametrized complexity theory.
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Logarithmic Sobolev Inequalities
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- The linear arrangement problem parameterized above guaranteed value
- Total Ordering Problem
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Kernelization: new upper and lower bound techniques
- Vertex cover problem parameterized above and below tight bounds
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Interval Completion Is Fixed Parameter Tractable
- Note on Max Lin-2 above average
- Cyclic ordering is NP-complete
- A new approach to cyclic ordering of 2D orientations using ternary relation algebras
- On Random Betweenness Constraints
- On Random Ordering Constraints
- A probabilistic approach to problems parameterized above or below tight bounds
- A Geometric Approach to Betweenness
- Title not available (Why is that?)
- Fixed-parameter complexity of minimum profile problems
Cited In (18)
- Parameterized complexity of MaxSat above average
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Approximating long cycle above Dirac's guarantee
- Title not available (Why is that?)
- Linear kernels and linear-time algorithms for finding large cuts
- Detours in directed graphs
- Betweenness parameterized above tight lower bound
- Large independent sets in subquartic planar graphs
- Confronting intractability via parameters
- Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Going far from degeneracy
- Finding detours is fixed-parameter tractable
- Turán’s Theorem Through Algorithmic Lens
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Large independent sets in triangle-free planar graphs
- Parameterized constraint satisfaction problems: a survey
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)
