All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables

Details All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables

2010-04-12

arxiv.org/abs/1004.1956v3

Computer Science

Data Structures and Algorithms

Scientific paper

A ternary Permutation-CSP is specified by a subset $\Pi$ of the symmetric group $\mathcal S_3$. 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 $\alpha$ of $V$ that maximizes the number of triples whose ordering (under $\alpha$) follows a permutation in $\Pi$. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.

Affiliated with

Also associated with

No associations

Rating

All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-262910