Critical Node Detection Problem Solving on GPU and in the Cloud
| Title | Critical Node Detection Problem Solving on GPU and in the Cloud |
| Publication Type | Conference Paper |
| Year of Publication | 2015 |
| Authors | Degenbaeva, C., Klusch, M. |
| Conference Name | 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded S |
| Date Published | aug |
| Keywords | Approximation algorithms, cloud computing, CNDP, critical node detection problem, data structures, Electronic mail, GPU, graph theory, graph-theoretical problem, graphics processing units, NP-complete problem, optimisation, parallel algorithms, Performance analysis, pubcrawl170112, Runtime |
| Abstract | The Critical Node Detection Problem (CNDP) is a well-known NP-complete, graph-theoretical problem with many real-world applications in various fields such as social network analysis, supply-chain network analysis, transport engineering, network immunization, and military strategic planning. We present the first parallel algorithms for CNDP solving in general, and for fast, approximated CND on GPU and in the cloud in particular. Finally, we discuss results of our experimental performance analysis of these solutions. |
| DOI | 10.1109/HPCC-CSS-ICESS.2015.8 |
| Citation Key | degenbaeva_critical_2015 |