@inproceedings{dd6463c3343241e99076f8854ed889f6,
title = "The secret santa problem",
abstract = "Consider a digraph where the vertices represent people and an arc (i,j) represents the possibility of i giving a gift to j. The basic question we pose is whether there is an anonymity-preserving {"}gift assignment{"} such that each person makes and receives exactly one gift, and such that no person i can infer the remaining gift assignments from the fact that i is assigned to give a gift to j. We formalize this problem as a graph property involving vertex disjoint circuit covers, give a polynomial algorithm to decide this property for any given graph and provide a computational validation of the algorithm.",
author = "Leo Liberti and Franco Raimondi",
year = "2008",
month = jan,
day = "1",
doi = "10.1007/978-3-540-68880-8\_26",
language = "English",
isbn = "354068865X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "271--279",
booktitle = "Algorithmic Aspects in Information and Management - 4th International Conference, AAIM 2008, Proceedings",
note = "4th International Conference on Algorithmic Aspects in Information and Management, AAIM 2008 ; Conference date: 23-06-2008 Through 25-06-2008",
}