Every ternary permutation constraint satisfaction problems parameterized above average has a kernel with a quadratic number of variables

G. Gutin, L.J.J. Iersel, van, M. Mnich, A. Yeo

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

22 Citaten (Scopus)

Samenvatting

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 every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.
Originele taal-2Engels
Pagina's (van-tot)151-163
TijdschriftJournal of Computer and System Sciences
Volume78
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2012

Vingerafdruk

Duik in de onderzoeksthema's van 'Every ternary permutation constraint satisfaction problems parameterized above average has a kernel with a quadratic number of variables'. Samen vormen ze een unieke vingerafdruk.

Citeer dit