کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6891634 1445268 2018 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Critical Node Detection Problem in networks: A survey
ترجمه فارسی عنوان
مشکل تشخیص گره در شبکه ها: یک نظرسنجی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
In networks, not all nodes have the same importance, and some are more important than others. The issue of finding the most important nodes in networks has been addressed extensively, particularly for nodes whose importance is related to network connectivity. These nodes are usually known as Critical Nodes. The Critical Node Detection Problem (CNDP) is the optimization problem that consists in finding the set of nodes, the deletion of which maximally degrades network connectivity according to some predefined connectivity metrics. Recently, this problem has attracted much attention, and depending on the predefined metric, different variants have been developed. In this survey, we review, classify and discuss several recent advances and results obtained for each variant, including theoretical complexity, exact solving algorithms, approximation schemes and heuristic approaches. We also prove new complexity results and induce some solving algorithms through relationships established between different variants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Science Review - Volume 28, May 2018, Pages 92-117
نویسندگان
, , ,