All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels

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

doi:10.1007/978-3-642-15775-2_28

All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels

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

Combinatorial Optimization - EIDMA

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)
Editors	M. Berg, de, U. Meyer
Place of Publication	Berlin
Publisher	Springer
Pages	326-337
ISBN (Print)	978-3-642-15774-5
DOIs	https://doi.org/10.1007/978-3-642-15775-2_28
Publication status	Published - 2010

Publication series

Name	Lecture Notes in Computer Science
Volume	6346
ISSN (Print)	0302-9743

Access to Document

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

Fingerprint Dive into the research topics of 'All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels'. Together they form a unique fingerprint.

Cite this

Gutin, G., Iersel, van, L. J. J., Mnich, M., & Yeo, A. (2010). All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels. In M. Berg, de, & U. Meyer (Eds.), Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I) (pp. 326-337). (Lecture Notes in Computer Science; Vol. 6346). Springer. https://doi.org/10.1007/978-3-642-15775-2_28

Gutin, G. ; Iersel, van, L.J.J. ; Mnich, M. ; Yeo, A. / All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels. Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I). editor / M. Berg, de ; U. Meyer. Berlin : Springer, 2010. pp. 326-337 (Lecture Notes in Computer Science).

@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",

}

Gutin, G, Iersel, van, LJJ, Mnich, M & Yeo, A 2010, All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels. in M Berg, de & U Meyer (eds), Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I). Lecture Notes in Computer Science, vol. 6346, Springer, Berlin, pp. 326-337. https://doi.org/10.1007/978-3-642-15775-2_28

All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels. / Gutin, G.; Iersel, van, L.J.J.; Mnich, M.; Yeo, A.

Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I). ed. / M. Berg, de; U. Meyer. Berlin : Springer, 2010. p. 326-337 (Lecture Notes in Computer Science; Vol. 6346).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels

AU - Gutin, G.

AU - Iersel, van, L.J.J.

AU - Mnich, M.

AU - Yeo, A.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

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

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

M3 - Conference contribution

SN - 978-3-642-15774-5

T3 - Lecture Notes in Computer Science

SP - 326

EP - 337

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

A2 - Berg, de, M.

A2 - Meyer, U.

PB - Springer

CY - Berlin

ER -

Gutin G, Iersel, van LJJ, Mnich M, Yeo A. All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels. In Berg, de M, Meyer U, editors, Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I). Berlin: Springer. 2010. p. 326-337. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-15775-2_28