Skip to main content Skip to main navigation

Publication

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, USA, IEEE Press, 2015.

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.