The anonymous subgraph problem

Andrea Bettinelli; Leo Liberti; Franco Raimondi; David Savourey

doi:10.1016/j.cor.2012.11.018

The anonymous subgraph problem

Andrea Bettinelli
, Leo Liberti
, Franco Raimondi
, David Savourey

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	973-979
Number of pages	7
Journal	Computers and Operations Research
Volume	40
Issue number	4
DOIs	https://doi.org/10.1016/j.cor.2012.11.018
Publication status	Published - 1 Apr 2013

Keywords

Anonymity
Anonymous routing
Graph topology
Secret Santa

Access to Document

10.1016/j.cor.2012.11.018

Cite this

@article{61ebdeaf7ec045d6b6ca41ab39955bbb,

title = "The anonymous subgraph problem",

abstract = "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.",

keywords = "Anonymity, Anonymous routing, Graph topology, Secret Santa",

author = "Andrea Bettinelli and Leo Liberti and Franco Raimondi and David Savourey",

year = "2013",

month = apr,

day = "1",

doi = "10.1016/j.cor.2012.11.018",

language = "English",

volume = "40",

pages = "973--979",

journal = "Computers and Operations Research",

issn = "0305-0548",

number = "4",

}

TY - JOUR

T1 - The anonymous subgraph problem

AU - Bettinelli, Andrea

AU - Liberti, Leo

AU - Raimondi, Franco

AU - Savourey, David

PY - 2013/4/1

Y1 - 2013/4/1

N2 - 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.

AB - 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.

KW - Anonymity

KW - Anonymous routing

KW - Graph topology

KW - Secret Santa

U2 - 10.1016/j.cor.2012.11.018

DO - 10.1016/j.cor.2012.11.018

M3 - Article

AN - SCOPUS:84872377440

SN - 0305-0548

VL - 40

SP - 973

EP - 979

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 4

ER -

The anonymous subgraph problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this