@inproceedings{779126c5ede241b0b0a1ca2cd60229af,

title = "All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels",

abstract = "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 a of V that maximizes the number of triples whose rearrangement (under a) follows a permutation in ¿. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.",

author = "G. Gutin and {Iersel, van}, L.J.J. and M. Mnich and A. Yeo",

year = "2010",

doi = "10.1007/978-3-642-15775-2_28",

language = "English",

isbn = "978-3-642-15774-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "326--337",

editor = "{Berg, de}, M. and U. Meyer",

booktitle = "Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)",

address = "Germany",

}