کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10346260 | 698778 | 2013 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Anonymous Subgraph Problem
ترجمه فارسی عنوان
مشکل زیرگرافی ناشناس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ناشناس مسیریابی ناشناس، سانتا راز توپولوژی گراف،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 4, April 2013, Pages 973-979
Journal: Computers & Operations Research - Volume 40, Issue 4, April 2013, Pages 973-979
نویسندگان
Andrea Bettinelli, Leo Liberti, Franco Raimondi, David Savourey,