Résumé
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.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 973-979 |
| Nombre de pages | 7 |
| journal | Computers and Operations Research |
| Volume | 40 |
| Numéro de publication | 4 |
| Les DOIs | |
| état | Publié - 1 avr. 2013 |
Empreinte digitale
Examiner les sujets de recherche de « The anonymous subgraph problem ». Ensemble, ils forment une empreinte digitale unique.Contient cette citation
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver