TY - GEN

T1 - All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables

AU - Gutin, Gregory

AU - Van Iersel, Leo

AU - Mnich, Matthias

AU - Yeo, Anders

PY - 2010

Y1 - 2010

N2 - A ternary Permutation-CSP is specified by a subset Π of the symmetric group S3. 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 all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.

AB - A ternary Permutation-CSP is specified by a subset Π of the symmetric group S3. 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 all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.

UR - http://www.scopus.com/inward/record.url?scp=78249260335&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15775-2_28

DO - 10.1007/978-3-642-15775-2_28

M3 - Article in proceedings

AN - SCOPUS:78249260335

SN - 3642157742

SN - 9783642157745

VL - 6346 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 326

EP - 337

BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings

T2 - 18th Annual European Symposium on Algorithms, ESA 2010

Y2 - 6 September 2010 through 8 September 2010

ER -