arrow
返回

The Anonymous Subgraph Problem

delete2013-04-01
delete1
delete
OA
AI
A
Andrea Bettinelli *
L
Leo Liberti
F
Franco Raimondi
D
David Savourey
DOI:10.1016/j.cor.2012.11.018delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
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. (C) 2012 Elsevier Ltd. All rights reserved.
Keyword:
Anonymity
Anonymous routing
Secret Santa
Graph topology
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

C
Computers and Operations Research
IF:
4.3
论文数:
6.5K
被引数:
2.3W

机构

U
university of milan
学者数:
1.6K
论文数: 673
被引数: 2.0W
E
ecole polytechnique
学者数:
52
论文数: 33
被引数: 3.4K
I
institut polytechnique de paris
学者数:
210
论文数: 111
被引数: 7.1K
学者 查看更多机构
引用论文

引用论文

CANDIDA INFECTION OF LOCAL NECROSIS IN SEVERE ACUTE PANCREATITIS IS ASSOCIATED WITH INCREASED MORTALITY
err2000-09-01
err0
errOAAI
errPeter Götzinger; Peter Wamser; Murat Barlan; Thomas Sautner; Raimund Jakesz; Reinhold Függer
err分享
err收藏
Emotional Abuse, Self-Blame, and Self-Silencing in Women With Irritable Bowel Syndrome
err2000-01-01
err0
PREAI
errAlisha Ali; Brenda B. Toner; Noreen Stuckless; Ruth Gallop; Nicholas E. Diamant; Michael I. Gould; Eva I. Vidins
err分享
err收藏
err分享
err收藏
Peroxidative oxidation of benzene and mesitylene by vanadium catalysts
err2004-12-01
err0
PREAI
errPatrícia M. Reis; José Armando L. Silva; João J.R. Fraústo da Silva; Armando J.L. Pombeiro
err分享
err收藏
The Structures of the Decaphenylmetallocenium Cations of Chromium and Cobalt
err1997-01-01
err0
PREAI
errLeslie D. Field; Trevor W. Hambley; Taian He,; Anthony F. Masters; Peter Turner
err分享
err收藏
Metallocene carbene chemistry
err2004-05-01
err0
PREAI
errG. Erker; G. Kehr; R. Fröhlich
err分享
err收藏
学者 查看更多内容