| Article ID: | iaor2013778 |
| Volume: | 40 |
| Issue: | 4 |
| Start Page Number: | 973 |
| End Page Number: | 979 |
| Publication Date: | Apr 2013 |
| Journal: | Computers and Operations Research |
| Authors: | Liberti Leo, Savourey David, Bettinelli Andrea, Raimondi Franco |
| Keywords: | graphs |
In this work we address the Anonymous Subgraph Problem (ASP). The problem asks to decide whether a directed graph contains anonymous subgraphs of a given family. This problem has a number of practical applications and here we describe three of them (Secret Santa Problem, anonymous routing, robust paths) that can be formulated as ASPs. Our main contributions are (i) a formalization of the anonymity property for a generic family of subgraphs, (ii) an algorithm to solve the ASP in time polynomial in the size of the graph under a set of conditions, and (iii) a thorough evaluation of our algorithms using various tests based both on randomly generated graphs and on real‐world instances.