Gutin, Gregory Z.Gregory Z.GutinIersel, Leo vanLeo vanIerselMnich, MatthiasMatthiasMnichYeo, AndersAndersYeo2020-01-242020-01-242012-01Journal of Computer and System Sciences (2012)http://hdl.handle.net/11420/4570A 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.en1090-2724Journal of computer and system sciences2012151163ElsevierInformatikEvery ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variablesJournal Article10.1016/j.jcss.2011.01.004Other