Rosicka, M;
Severini, S;
(2016)
Permutation graphs and unique games.
Preview |
Text
Rosicka_Permutation_graphs_unique_games.pdf Download (197kB) | Preview |
Abstract
We study the value of unique games as a graph-theoretic parameter. This is obtained by labeling edges with permutations. We describe the classical value of a game as well as give a necessary and sufficient condition for the existence of an optimal assignment based on a generalisation of permutation graphs and graph bundles. In considering some special cases, we relate XOR games to EDGE BIPARTIZATION, and define an edge-labeling with permutations from Latin squares.
| Type: | Working / discussion paper |
|---|---|
| Title: | Permutation graphs and unique games |
| Open access status: | An open access version is available from UCL Discovery |
| Language: | English |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/1526393 |
Archive Staff Only
 |
View Item |
