返回
The Anonymous Subgraph Problem
DOI:10.1016/j.cor.2012.11.018.png)
摘要
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总结
对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
2.3W
机构
引用论文
CANDIDA INFECTION OF LOCAL NECROSIS IN SEVERE ACUTE PANCREATITIS IS ASSOCIATED WITH INCREASED MORTALITY
Shock
IF0

