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.
The anonymous subgraph problem / A. Bettinelli, L. Liberti, F. Raimondi, D. Savourey. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 40:4(2013 Apr), pp. 973-979.
|Titolo:||The anonymous subgraph problem|
BETTINELLI, ANDREA (Primo)
|Parole Chiave:||Anonymity ; Anonymous routing ; Secret Santa ; Graph topology|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||apr-2013|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.cor.2012.11.018|
|Appare nelle tipologie:||01 - Articolo su periodico|