The critical node detection problem in networks: a survey. (English) Zbl 1387.68186
Summary: 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68-02 | Research exposition (monographs, survey articles) pertaining to computer science |
| 05C40 | Connectivity |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
critical node; important node; node-deletion problem; complex network; combinatorial optimization; complexity; approximation schemes; graph connectivityReferences:
| [1] | Kempe, D.; Kleinberg, J.; Tardos, É., Influential nodes in a diffusion model for social networks, (Automata, Languages and Programming (2005), Springer), 1127-1138 · Zbl 1084.91053 |
| [2] | Corley, H.; Sha, D. Y., Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 4, 157-160 (1982) · Zbl 0488.90069 |
| [3] | Li, C.-T.; Lin, S.-D.; Shan, M.-K., Finding influential mediators in social networks, (Proceedings of the 20th International Conference Companion on World Wide Web (2011), ACM), 75-76 |
| [4] | Borgatti, S. P., Identifying sets of key players in a social network, Comput. Math. Org. Theory, 12, 1, 21-34 (2006) · Zbl 1198.91180 |
| [5] | Hellwig, A.; Volkmann, L., Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math., 308, 15, 3265-3296 (2008) · Zbl 1160.05038 |
| [6] | Fjällström, P.-O., Algorithms for Graph Partitioning: A Survey, Vol. 3 (1998), Linköping University Electronic Press Linköping |
| [7] | Pothen, A., Graph partitioning algorithms with applications to scientific computing, (Parallel Numerical Algorithms (1997), Springer), 323-368 · Zbl 0868.68090 |
| [8] | Buluç, A.; Meyerhenke, H.; Safro, I.; Sanders, P.; Schulz, C., Recent advances in graph partitioning, (Algorithm Engineering (2016), Springer), 117-158 |
| [9] | Goldschmidt, O.; Hochbaum, D. S., A polynomial algorithm for the \(k\)-cut problem for fixed k, Math. Oper. Res., 19, 1, 24-37 (1994) · Zbl 0809.90125 |
| [10] | He, X., An improved algorithm for the planar 3-cut problem, J. Algorithms, 12, 1, 23-37 (1991) · Zbl 0712.68075 |
| [11] | Costa, M.-C.; Létocart, L.; Roupin, F., Minimal multicut and maximal integer multiflow: A survey, European J. Oper. Res., 162, 1, 55-69 (2005) · Zbl 1132.90306 |
| [12] | Garg, N.; Vazirani, V. V.; Yannakakis, M., Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 1, 3-20 (1997) · Zbl 0873.68075 |
| [13] | Guo, J.; Niedermeier, R., Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 3, 124-135 (2005) · Zbl 1081.68070 |
| [14] | Chopra, S.; Rao, M. R., On the multiway cut polyhedron, Networks, 21, 1, 51-89 (1991) · Zbl 0746.90077 |
| [15] | Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894 (1994) · Zbl 0809.68075 |
| [16] | Chopra, S.; Owen, J. H., Extended formulations for the A-cut problem, Math. Program., 73, 1, 7-30 (1996) · Zbl 0848.90119 |
| [17] | Avidor, A.; Langberg, M., The multi-multiway cut problem, Theoret. Comput. Sci., 377, 1-3, 35-42 (2007) · Zbl 1115.68171 |
| [18] | Bui, T. N.; Jones, C., Finding good approximate vertex and edge partitions is NP-hard, Inform. Process. Lett., 42, 3, 153-159 (1992) · Zbl 0764.68061 |
| [19] | Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 2, 177-189 (1979) · Zbl 0432.05022 |
| [20] | Fukuyama, J., NP-completeness of the planar separator problems, J. Graph Algorithms Appl., 10, 2, 317-328 (2006) · Zbl 1178.68378 |
| [21] | de Souza, C.; Balas, E., The vertex separator problem: algorithms and computations, Math. Program., 103, 3, 609-631 (2005) · Zbl 1099.90069 |
| [22] | Biha, M. D.; Meurs, M.-J., An exact algorithm for solving the vertex separator problem, J. Global Optim., 49, 3, 425-434 (2011) · Zbl 1211.90260 |
| [23] | U. Benlic, J.-K. Hao, Breakout local search for the vertex separator problem, in: IJCAI, 2013, pp. 461-467.; U. Benlic, J.-K. Hao, Breakout local search for the vertex separator problem, in: IJCAI, 2013, pp. 461-467. |
| [24] | Chen, J.; Liu, Y.; Lu, S., An improved parameterized algorithm for the minimum node multiway cut problem, Algorithmica, 55, 1, 1-13 (2009) · Zbl 1194.68168 |
| [25] | Guillemot, S., Fpt algorithms for path-transversals and cycle-transversals problems in graphs, (International Workshop on Parameterized and Exact Computation (2008), Springer), 129-140 · Zbl 1142.68599 |
| [26] | Călinescu, G.; Fernandes, C. G.; Reed, B., Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, J. Algorithms, 48, 2, 333-359 (2003) · Zbl 1079.68069 |
| [27] | Papadopoulos, C., Restricted vertex multicut on permutation graphs, Discrete Appl. Math., 160, 12, 1791-1797 (2012) · Zbl 1246.05153 |
| [28] | Guo, J.; Hüffner, F.; Kenar, E.; Niedermeier, R.; Uhlmann, J., Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, European J. Oper. Res., 186, 2, 542-553 (2008) · Zbl 1138.90345 |
| [29] | Marx, D., Parameterized graph separation problems, Theoret. Comput. Sci., 351, 3, 394-406 (2006) · Zbl 1086.68104 |
| [30] | Michael, R. G.; David, S. J., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), WH Freeman & Co.: WH Freeman & Co. San Francisco · Zbl 0411.68039 |
| [31] | Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 2, 219-230 (1980) · Zbl 0436.68029 |
| [32] | Yannakakis, M., Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 2, 310-327 (1981) · Zbl 0468.05044 |
| [33] | Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36, 7, 2193-2200 (2009) · Zbl 1158.90411 |
| [34] | Boginski, V.; Commander, C. W., Identifying critical nodes in protein-protein interaction networks, Clustering Challenges Biol. Netw., 153-167 (2009) |
| [35] | Tomaino, V.; Arulselvan, A.; Veltri, P.; Pardalos, P. M., Studying connectivity properties in human protein-protein interaction network in cancer pathway, (Data Mining for Biomarker Discovery (2012), Springer), 187-197 |
| [36] | Dinh, T. N.; Thai, M. T., Precise structural vulnerability assessment via mathematical programming, (Military Communications Conference, 2011-MILCOM 2011 (2011), IEEE), 1351-1356 |
| [37] | Shen, Y.; Nguyen, N. P.; Xuan, Y.; Thai, M. T., On the discovery of critical links and nodes for assessing network vulnerability, IEEE/ACM Trans. Netw., 21, 3, 963-973 (2013) |
| [38] | Shen, Y.; Dinh, T. N.; Thai, M. T., Adaptive algorithms for detecting critical links and nodes in dynamic networks, (Military Communications Conference, MILCOM 2012 (2012), Citeseer), 1-6 |
| [39] | Nguyen, D. T.; Shen, Y.; Thai, M. T., Detecting critical nodes in interdependent power networks for vulnerability assessment, Smart Grid, IEEE Trans., 4, 1, 151-159 (2013) |
| [40] | He, J.; Liang, H.; Yuan, H., Controlling infection by blocking nodes and links simultaneously, (Internet and Network Economics (2011), Springer), 206-217 |
| [41] | Aspnes, J.; Chang, K.; Yampolskiy, A., Inoculation strategies for victims of viruses and the sum-of-squares partition problem, (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005), Society for Industrial and Applied Mathematics), 43-52 · Zbl 1297.68258 |
| [42] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, Vol. 6 (1976), Macmillan: Macmillan London · Zbl 1226.05083 |
| [43] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Vol. 57 (2004), Elsevier · Zbl 1050.05002 |
| [44] | Jungck, J. R.; Dick, G.; Dick, A. G., Computer-assisted sequencing, interval graphs, and molecular evolution, Biosystems, 15, 3, 259-273 (1982) |
| [45] | Pal, A.; Pal, M., Interval tree and its applications, Adv. Model. Optim., 11, 3, 211-224 (2009) · Zbl 1192.68491 |
| [46] | Shen, S.; Smith, J. C., Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks, 60, 2, 103-119 (2012) · Zbl 1251.90376 |
| [47] | Robertson, N.; Seymour, P. D., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 |
| [48] | Bodlaender, H. L., Classes of Graphs with Bounded Tree-Width (1986), Department of Computer Science, University of Utrecht, Netherlands |
| [49] | Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernet., 11, 1-2, 1 (1994) · Zbl 0804.68101 |
| [50] | Bodlaender, H. L., Treewidth: characterizations, applications, and computations, WG, 4271, 1-14 (2006) · Zbl 1167.68404 |
| [51] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (2012), Springer Science & Business Media · Zbl 0914.68076 |
| [52] | Flum, J.; Grohe, M., Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series) (2006), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 1143.68016 |
| [53] | Cohen, R.; Erez, K.; Ben-Avraham, D.; Havlin, S., Resilience of the internet to random breakdowns, Phys. Rev. Lett., 85, 21, 4626 (2000) |
| [54] | Albert, R.; Jeong, H.; Barabási, A.-L., Error and attack tolerance of complex networks, Nature, 406, 6794, 378-382 (2000) |
| [55] | Faramondi, L.; Oliva, G.; Setola, R.; Pascucci, F.; Amideo, A. E.; Scaparra, M. P., Performance analysis of single and multi-objective approaches for the critical node detection problem, (International Conference on Optimization and Decision Science (2017), Springer), 315-324 |
| [56] | Festa, P.; Pardalos, P. M.; Resende, M. G., Feedback set problems, (Handbook of Combinatorial Optimization (1999), Springer), 209-258 · Zbl 1253.90193 |
| [57] | Schieber, B.; Bar-Noy, A.; Khuller, S., The Complexity of Finding Most Vital Arcs and Nodes, ((1995), University of Maryland at College Park: University of Maryland at College Park College Park, MD, USA) |
| [58] | Khachiyan, L.; Boros, E.; Borys, K.; Elbassioni, K.; Gurvich, V.; Rudolf, G.; Zhao, J., On short paths interdiction problems: total and node-wise limited interdiction, Theory Comput. Syst., 43, 2, 204-233 (2008) · Zbl 1148.68036 |
| [59] | Choi, H.-A.; Nakajima, K.; Rim, C. S., Graph bipartization and via minimization, SIAM J. Discrete Math., 2, 1, 38-47 (1989) · Zbl 0677.68036 |
| [60] | Marx, D., Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 4, 747-768 (2010) · Zbl 1220.05066 |
| [61] | Marx, D.; Schlotter, I., Obtaining a planar graph by vertex deletion, Algorithmica, 62, 3-4, 807-822 (2012) · Zbl 1239.05044 |
| [62] | Arulselvan, A.; Commander, C. W.; Shylo, O.; Pardalos, P. M., Cardinality- constrained critical node detection problem, (Performance Models and Risk Management in Communications Systems (2011), Springer), 79-91 · Zbl 1213.90078 |
| [63] | Dinh, T. N.; Xuan, Y.; Thai, M. T.; Park, E.; Znati, T., On approximation of new optimization methods for assessing network vulnerability, (INFOCOM, 2010 Proceedings IEEE (2010), IEEE), 1-9 |
| [64] | Shen, S.; Smith, J. C.; Goli, R., Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optim., 9, 3, 172-188 (2012) · Zbl 1254.90280 |
| [65] | Addis, B.; Di Summa, M.; Grosso, A., Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math., 161, 16, 2349-2360 (2013) · Zbl 1285.05042 |
| [66] | Berger, A.; Grigoriev, A.; Zwaan, R., Complexity and approximability of the k-way vertex cut, Networks, 63, 2, 170-178 (2014) · Zbl 1386.05148 |
| [67] | Di Summa, M.; Grosso, A.; Locatelli, M., Complexity of the critical node problem over trees, Comput. Oper. Res., 38, 12, 1766-1774 (2011) · Zbl 1215.90016 |
| [68] | Lalou, M.; Tahraoui, M. A.; Kheddouci, H., Component-cardinality-constrained critical node problem in graphs, Discrete Appl. Math., 210, 150-163 (2016) · Zbl 1339.05374 |
| [69] | Freeman, L. C., Centrality in social networks conceptual clarification, Soc. Netw., 1, 3, 215-239 (1979) |
| [70] | Chartrand, G., Introduction to graph theory (2006), Tata McGraw-Hill Education |
| [71] | Bader, D. A.; Kintali, S.; Madduri, K.; Mihail, M., Approximating betweenness centrality, (Algorithms and Models for the Web-Graph (2007), Springer), 124-137 · Zbl 1136.68320 |
| [72] | Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol., 25, 2, 163-177 (2001) · Zbl 1051.91088 |
| [73] | Di Summa, M.; Grosso, A.; Locatelli, M., Branch and cut algorithms for detecting critical nodes in undirected graphs, Comput. Optim. Appl., 53, 3, 649-680 (2012) · Zbl 1264.90170 |
| [74] | Oosten, M.; Rutten, J. H.; Spieksma, F. C., Disconnecting graphs by removing vertices: a polyhedral approach, Stat. Neerl., 61, 1, 35-60 (2007) · Zbl 1122.90088 |
| [75] | Arulselvan, A.; Commander, C. W.; Pardalos, P. M.; Shylo, O., Managing network risk via critical node identification, (Risk Management in Telecommunication Networks (2007), Springer) |
| [76] | Ventresca, M.; Aleman, D., A fast greedy algorithm for the critical node detection problem, (Combinatorial Optimization and Applications (2014), Springer), 603-612 · Zbl 1433.05302 |
| [77] | Dinh, T. N.; Thai, M. T., Assessing attack vulnerability in networks with uncertainty, (IEEE International Conference on Computer Communications (INFOCOM) (2015), IEEE) |
| [78] | Ventresca, M.; Aleman, D., A derandomized approximation algorithm for the critical node detection problem, Comput. Oper. Res., 43, 261-270 (2014) · Zbl 1348.90609 |
| [79] | Ventresca, M.; Aleman, D., A region growing algorithm for detecting critical nodes, (Combinatorial Optimization and Applications (2014), Springer), 593-602 · Zbl 1433.05301 |
| [80] | Ventresca, M.; Aleman, D., A randomized algorithm with local search for containment of pandemic disease spread, Comput. Oper. Res., 48, 11-19 (2014) · Zbl 1348.92011 |
| [81] | Ventresca, M., Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem, Comput. Oper. Res., 39, 11, 2763-2775 (2012) · Zbl 1251.90342 |
| [82] | Veremyev, A.; Prokopyev, O. A.; Pasiliao, E. L., An integer programming framework for critical elements detection in graphs, J. Combin. Optim., 28, 1, 233-273 (2014) · Zbl 1303.90120 |
| [83] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., A general evolutionary framework for different classes of critical node problems, Eng. Appl. Artif. Intell., 55, 128-145 (2016) |
| [84] | Hermelin, D.; Kaspi, M.; Komusiewicz, C.; Navon, B., Parameterized complexity of critical node cuts, Theoret. Comput. Sci., 651, 62-75 (2016) · Zbl 1359.68135 |
| [85] | Veremyev, A.; Boginski, V.; Pasiliao, E. L., Exact identification of critical nodes in sparse networks via new compact formulations, Optim. Lett., 8, 4, 1245-1259 (2014) · Zbl 1292.90260 |
| [86] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., VNS solutions for the critical node problem, Electron. Notes Discrete Math., 47, 37-44 (2015) · Zbl 1362.68255 |
| [87] | Addis, B.; Aringhieri, R.; Grosso, A.; Hosteins, P., Hybrid constructive heuristics for the critical node problem, Ann. Oper. Res., 238, 1-2, 637-649 (2016) · Zbl 1334.90185 |
| [88] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., Local search metaheuristics for the critical node problem, Networks, 67, 3, 209-221 (2016) |
| [89] | Pullan, W., Heuristic identification of critical nodes in sparse real-world graphs, J. Heuristics, 21, 5, 577-598 (2015) |
| [90] | Purevsuren, D.; Cui, G.; Win, N. N.H.; Wang, X., Heuristic algorithm for identifying critical nodes in graphs, Adv. Comput. Sci.: Int. J., 5, 3, 1-4 (2016) |
| [91] | Y. Shen, M.T. Thai, Network vulnerability assessment under cascading failures, in: 2013 IEEE Global Communications Conference, GLOBECOM 2013, Atlanta, GA, USA, December 9-13, 2013, 2013, pp. 1526-1531.; Y. Shen, M.T. Thai, Network vulnerability assessment under cascading failures, in: 2013 IEEE Global Communications Conference, GLOBECOM 2013, Atlanta, GA, USA, December 9-13, 2013, 2013, pp. 1526-1531. |
| [92] | Ventresca, M.; Harrison, K. R.; Ombuki-Berman, B. M., An experimental evaluation of multi-objective evolutionary algorithms for detecting critical nodes in complex networks, (European Conference on the Applications of Evolutionary Computation (2015), Springer), 164-176 |
| [93] | Balas, E.; de Souza, C. C., The vertex separator problem: a polyhedral investigation, Math. Program., 103, 3, 583-608 (2005) · Zbl 1099.90065 |
| [94] | Dinh, T. N.; Thai, M. T., Network under joint node and link attacks: Vulnerability assessment methods and analysis, IEEE/ACM Trans. Netw., 23, 3, 1001-1011 (2015) |
| [95] | Cormen, T. H., Introduction to Algorithms (2009), MIT press · Zbl 1187.68679 |
| [96] | Ventresca, M.; Harrison, K. R.; Ombuki-Berman, B. M., The bi-objective critical node detection problem, European J. Oper. Res., 265, 3, 895-908 (2018) · Zbl 1374.90085 |
| [97] | Wood, R. K., Deterministic network interdiction, Math. Comput. Modelling, 17, 2, 1-18 (1993) · Zbl 0800.90772 |
| [98] | Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete problems, (Proceedings of the Sixth Annual ACM Symposium on Theory of Computing (1974), ACM), 47-63 |
| [99] | Dinur, I.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. of Math., 439-485 (2005) · Zbl 1084.68051 |
| [100] | Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), (Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on (1996), IEEE), 627-636 |
| [101] | Myung, Y.-S.; Kim, H.-j., A cutting plane algorithm for computing k-edge survivability of a network, European J. Oper. Res., 156, 3, 579-589 (2004) · Zbl 1056.90015 |
| [102] | Raghavan, P.; Tompson, C. D., Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 4, 365-374 (1987) · Zbl 0651.90052 |
| [103] | Hansen, P.; Mladenović, N.; Pérez, J. A.M., Variable neighbourhood search: methods and applications, Ann. Oper. Res., 175, 1, 367-407 (2010) · Zbl 1185.90211 |
| [104] | Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search: Framework and applications, (Handbook of Metaheuristics (2010), Springer), 363-397 |
| [105] | Resendel, M. G.; Ribeiro, C. C., Grasp with path-relinking: recent advances and applications, (Metaheuristics: Progress As Real Problem Solvers (2005), Springer), 29-63 |
| [106] | Purevsuren, D.; Cui, G.; Qu, M.; Win, N. N.H., Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs, IAENG Int. J. Comput. Sci., 44, 2 (2017) |
| [107] | Glover, F., Exterior path relinking for zero-one optimization, Int. J. Appl. Metaheuristic Comput., 5, 3, 1-8 (2014) |
| [108] | Y. Zhou, J.-K. Hao, F. Glover, Memetic search for identifying critical nodes in sparse graphs, 2017. ArXiv Preprint arXiv:1705.04119; Y. Zhou, J.-K. Hao, F. Glover, Memetic search for identifying critical nodes in sparse graphs, 2017. ArXiv Preprint arXiv:1705.04119 |
| [109] | Moscato, P.; Cotta, C., Memetic algorithms, Handb. Appl. Optim., 157, 168 (2002) |
| [110] | Zhou, Y.; Hao, J.-K., A fast heuristic algorithm for the critical node problem, (Proceedings of the Genetic and Evolutionary Computation Conference Companion (2017), ACM), 121-122 |
| [111] | Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: A survey of the state of the art, Swarm Evol. Comput., 1, 1, 32-49 (2011) |
| [112] | Veremyev, A.; Prokopyev, O. A.; Pasiliao, E. L., Critical nodes for distance-based connectivity and related problems in graphs, Networks, 66, 3, 170-195 (2015) |
| [113] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., A preliminary analysis of the distance based critical node problem, Electron. Notes Discrete Math., 55, 25-28 (2016) · Zbl 1356.05030 |
| [114] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, Discrete Appl. Math. (2018) |
| [115] | Paudel, N.; Georgiadis, L.; Italiano, G. F., Computing critical nodes in directed graphs, (2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, ALENEX (2017), SIAM), 43-57 · Zbl 1430.68235 |
| [116] | Khot, S., Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique, SIAM J. Comput., 36, 4, 1025-1071 (2006) · Zbl 1127.68035 |
| [117] | Barefoot, C. A.; Entringer, R.; Swart, H., Vulnerability in graphs -a comparative survey, J. Combin. Math. Combin. Comput., 1, 38, 13-22 (1987) · Zbl 0646.05042 |
| [118] | Bagga, K. S.; Beineke, L. W.; Goddard, W. D.; Lipman, M. J.; Pippert, R. E., A survey of integrity, Discrete Appl. Math., 37, 13-28 (1992) · Zbl 0778.05041 |
| [119] | Drange, P. G.; Dregi, M. S.; van’t Hof, P., On the computational complexity of vertex integrity and component order connectivity, (International Symposium on Algorithms and Computation (2014), Springer), 285-297 · Zbl 1352.68103 |
| [120] | Yannakakis, M., Node-and edge-deletion NP-complete problems, (Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (1978), ACM), 253-264 · Zbl 1282.68131 |
| [121] | Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625 (1979) · Zbl 0423.05039 |
| [122] | Alimonti, P.; Kann, V., Hardness of approximating problems on cubic graphs, (Algorithms and Complexity (1997), Springer), 288-298 |
| [123] | Balas, E.; Yu, C. S., On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 2, 247-253 (1989) · Zbl 0661.05036 |
| [124] | Gavril, F., Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett., 73, 5, 181-188 (2000) · Zbl 1339.05287 |
| [125] | Hayward, R. B., Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 3, 200-208 (1985) · Zbl 0551.05055 |
| [126] | Lozano, M.; García-Martínez, C.; Rodríguez, F. J.; Trujillo, H. M., Optimizing network attacks by artificial bee colony, Inform. Sci., 377, 30-50 (2017) |
| [127] | Faramondi, L.; Oliva, G.; Pascucci, F.; Panzieri, S.; Setola, R., Critical node detection based on attacker preferences, (Control and Automation, MED, 2016 24th Mediterranean Conference on (2016), IEEE), 773-778 |
| [128] | Faramondi, L.; Oliva, G.; Setola, R.; Pascucci, F.; Amideo, A. E.; Scaparra, M. P., Performance analysis of single and multi-objective approaches for the critical node detection problem, (International Conference on Optimization and Decision Science (2017), Springer), 315-324 |
| [129] | Karaboga, D.; Basturk, B., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, J. Global Optim., 39, 3, 459-471 (2007) · Zbl 1149.90186 |
| [130] | Faramondi, L.; Setola, R.; Panzieri, S.; Pascucci, F.; Oliva, G., Finding critical nodes in infrastructure networks, Int. J. Crit. Infrastruct. Prot. (2017) |
| [131] | Davis, T. A.; Hu, Y., The university of florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1, 1 (2011) · Zbl 1365.65123 |
| [132] | Xiao, M., Simple and improved parameterized algorithms for multiterminal cuts, Theory Comput. Syst., 46, 4, 723-736 (2010) · Zbl 1213.68472 |
| [133] | Schaeffer, S. E., Graph clustering, Comput. Sci. Rev., 1, 1, 27-64 (2007) · Zbl 1302.68237 |
| [134] | Fan, N.; Pardalos, P. M., Robust optimization of graph partitioning and critical node detection in analyzing networks, (Combinatorial Optimization and Applications (2010), Springer), 170-183 · Zbl 1311.90163 |
| [135] | Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; VanBriesen, J.; Glance, N., Cost-effective outbreak detection in networks, (Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2007), ACM), 420-429 |
| [136] | Kuhlman, C. J.; Kumar, V. A.; Marathe, M. V.; Ravi, S.; Rosenkrantz, D. J., Finding critical nodes for inhibiting diffusion of complex contagions in social networks, (Machine Learning and Knowledge Discovery in Databases (2010), Springer), 111-127 |
| [137] | Arulselvan, A., Network Model for Disaster Management (2009), University of Florida |
| [138] | Callahan, D.; Shakarian, P.; Nielsen, J.; Johnson, A. N., Shaping operations to attack robust terror networks, (Social Informatics, SocialInformatics, 2012 International Conference on (2012), IEEE), 13-18 |
| [139] | Commander, C. W.; Pardalos, P. M.; Ryabchenko, V.; Uryasev, S.; Zrazhevsky, G., The wireless network jamming problem, J. Combin. Optim., 14, 4, 481-498 (2007) · Zbl 1149.90124 |
| [140] | Pawson, T.; Nash, P., Protein-protein interactions define specificity in signal transduction, Genes Dev., 14, 9, 1027-1047 (2000) |
| [141] | Prieto, C.; De Las Rivas, J., APID: agile protein interaction DataAnalyzer, Nucleic Acids Res., 34, suppl. 2, W298-W302 (2006) |
| [142] | Westermarck, J.; Ivaska, J.; Corthals, G. L., Identification of protein interactions involved in cellular signaling, Mol. Cell. Proteomics, 12, 7, 1752-1763 (2013) |
| [143] | Yan, C.; Wu, F.; Jernigan, R. L.; Dobbs, D.; Honavar, V., Characterization of protein-protein interfaces, Protein J., 27, 1, 59-70 (2008) |
| [144] | Jhoti, H.; Leach, A. R., Structure-based Drug Discovery (2007), Springer |
| [145] | Liljefors, T.; Krogsgaard-Larsen, P.; Madsen, U., Textbook of Drug Design and Discovery (2002), CRC Press |
| [146] | Grubesic, T. H.; Matisziw, T. C.; Murray, A. T.; Snediker, D., Comparative approaches for assessing network vulnerability, Int. Reg. Sci. Rev., 31, 1, 88-112 (2008) |
| [147] | Clark, B. N.; Colbourn, C. J.; Johnson, D. S., Unit disk graphs, Discrete Math., 86, 1, 165-177 (1990) · Zbl 0739.05079 |
| [148] | Kleinberg, J., The small-world phenomenon: An algorithmic perspective, (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (2000), ACM), 163-170 · Zbl 1296.05181 |
| [149] | Gao, J.; Buldyrev, S. V.; Stanley, H. E.; Havlin, S., Networks formed from interdependent networks, Nature Phys., 8, 1, 40-48 (2012) |
| [150] | Huang, X.; Gao, J.; Buldyrev, S. V.; Havlin, S.; Stanley, H. E., Robustness of interdependent networks under targeted attack, Phys. Rev. E, 83, 6, 065101 (2011) |
| [151] | Parshani, R.; Buldyrev, S. V.; Havlin, S., Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition, Phys. Rev. Lett., 105, 4, 048701 (2010) |
| [152] | Fan, N.; Xu, H.; Pan, F.; Pardalos, P. M., Economic analysis of the N- k power grid contingency selection and evaluation by graph algorithms and interdiction methods, Energy Syst., 2, 3-4, 313-324 (2011) |
| [153] | Ovelgonne, M.; Kang, C.; Sawant, A.; Subrahmanian, V., Covertness centrality in networks, (Advances in Social Networks Analysis and Mining, ASONAM, 2012 IEEE/ACM International Conference on (2012), IEEE), 863-870 |
| [154] | Petersen, R. R.; Rhodes, C. J.; Wiil, U. K., Node removal in criminal networks, (Intelligence and Security Informatics Conference, EISIC, 2011 European (2011), IEEE), 360-365 |
| [155] | Krebs, V., Uncloaking terrorist networks, First Monday, 7, 4 (2002) |
| [156] | Christakis, N. A.; Fowler, J. H., Social network sensors for early detection of contagious outbreaks, PLoS One, 5, 9, e12948 (2010) |
| [157] | Krause, A.; Leskovec, J.; Guestrin, C.; VanBriesen, J.; Faloutsos, C., Efficient sensor placement optimization for securing large water distribution networks, J. Water Resour. Plan. Manage., 134, 6, 516-526 (2008) |
| [158] | Pinto, P. C.; Thiran, P.; Vetterli, M., Locating the source of diffusion in large-scale networks, Phys. Rev. Lett., 109, 6, 068702 (2012) |
| [159] | Pastor-Satorras, R.; Vespignani, A., Immunization of complex networks, Phys. Rev. E, 65, 3, 036104 (2002) |
| [160] | Kuhlman, C. J.; Tuli, G.; Swarup, S.; Marathe, M. V.; Ravi, S., Blocking simple and complex contagion by edge removal, (Data Mining, ICDM, 2013 IEEE 13th International Conference on (2013), IEEE), 399-408 |
| [161] | Lokhov, A. Y.; Mézard, M.; Ohta, H.; Zdeborová, L., Inferring the origin of an epidemic with a dynamic message-passing algorithm, Phys. Rev. E, 90, 1, 012801 (2014) |
| [162] | Shah, D.; Zaman, T., Rumors in a network: Who’s the culprit?, IEEE Trans. Inform. Theory, 57, 8, 5163-5181 (2011) · Zbl 1366.91126 |
| [163] | Cohen, R.; Havlin, S.; Ben-Avraham, D., Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett., 91, 24, 247901 (2003) |
| [164] | Tao, Z.; Zhongqian, F.; Binghong, W., Epidemic dynamics on complex networks, Prog. Natural Sci., 16, 5, 452-457 (2006) · Zbl 1121.92063 |
| [165] | Centola, D.; Macy, M., Complex contagions and the weakness of long ties1, Amer. J. Sociol., 113, 3, 702-734 (2007) |
| [166] | Lalou, M.; Kheddouci, H., Least squares method for diffusion source localization in complex networks, (International Workshop on Complex Networks and their Applications (2016), Springer), 473-485 |
| [167] | Bovy, P.; Thijs, R., Modelling for transportation systems planning, ISTE (2002), DUP Satellite |
| [168] | Vitoriano, B.; Ortuño, M. T.; Tirado, G.; Montero, J., A multi-criteria optimization model for humanitarian aid distribution, J. Global Optim., 51, 2, 189-208 (2011) · Zbl 1230.90175 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
