Efficient heuristic algorithm for identifying critical nodes in planar networks

The critical node problem (CNP) removes a limited number of nodes from a network in order to achieve the minimum pair-wise connectivity in the remaining network. In this paper, we present a heuristic algorithm for solving the CNP on planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. This enables us to develop a computationally efficient heuristic algorithm for solving the CNP. The proposed algorithm is tested on randomly generated planar networks. The computational experiments show the superiority of this algorithm compared with other algorithms. Furthermore, we examine how the proposed algorithm can be used for a variant of the CNP, called the cardinality-constrained critical node problem. (C) 2019 Elsevier Ltd. All rights reserved.