Publikation

Critical Node Detection Problem Solving on GPU and in the Cloud

Cholpon Degenbaeva, Matthias Klusch

In: Proc. of 17th IEEE International Conference on High Performance Computing and Communications. IEEE International Conference on High Performance Computing and Communications (HPCC-15) August 24-26 New York (Newark) NY United States IEEE Press 2015.

Abstrakt

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.

pCND-HPCC15.pdf (pdf, 407 KB)

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence