The Critical Node Detection Problem in networks: A survey
| Autor: | Hamamache Kheddouci, Mohammed Lalou, Mohammed Amin Tahraoui |
|---|---|
| Přispěvatelé: | Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Kheddouci, Hamamache |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Theoretical computer science Optimization problem General Computer Science Heuristic (computer science) Computer science Node (networking) 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Network connectivity 01 natural sciences Theoretical Computer Science Set (abstract data type) [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] 010201 computation theory & mathematics Metric (mathematics) ComputingMilieux_MISCELLANEOUS |
| Zdroj: | Computer Science Review Computer Science Review, Elsevier, 2018, 28, pp.92-117 |
| ISSN: | 1574-0137 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect