Visible to the public Critical Node Detection Problem Solving on GPU and in the Cloud

TitleCritical Node Detection Problem Solving on GPU and in the Cloud
Publication TypeConference Paper
Year of Publication2015
AuthorsDegenbaeva, C., Klusch, M.
Conference Name2015 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 Publishedaug
KeywordsApproximation 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

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.

Citation Keydegenbaeva_critical_2015