Options
Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
Publikationstyp
Journal Article
Date Issued
2012-01
Sprache
English
TORE-URI
Volume
78
Start Page
151
End Page
163
Citation
Journal of Computer and System Sciences (2012)
Publisher DOI
Publisher
Elsevier
A ternary Permutation-CSP is specified by a subset Π of the symmetric group . An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering α of V that maximizes the number of triples whose rearrangement (under α) follows a permutation in Π. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.
DDC Class
004: Informatik