Paper Info
Title
Dynamically Exchanging Nodes of the Critical Node Problem
Abstract
The Critical Node Problem (CNP) aims to identify k nodes from an undirected graph G=(V,E), in order to minimize the number of pairwise connected nodes in the residual graph after deleting these k nodes. This problem has a wide range of applications in the fields of cyber security, disease control, biological analysis, social network, etc. The CNP is known to be NP-hard, and heuristics are commonly used to solve large-scale CNP instances, among which the node-exchange operation is a basic move operator widely adopted by local-search based heuristics. Given an initial CNP solution consisting of k nodes, there are totally k×(|V|−k) possible node-exchange operations. The current best algorithm requires a complexity of O((|V|−k)×(|V|+|E|+k×D(G))) to evaluate all these operations (|V| denotes the number of nodes, |E| denotes the number of edges, D(G) denotes the maximum degree of the node in graph G).In this paper, a series of dynamic data structures are implemented to reduce the above complexity to O((|V|−k)×(|V|+|E|)), so as to improve the efficiency of local search.
Year
DOI
Venue
2018
10.1109/CCIS.2018.8691236
2018 5th IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS)
Keywords
Field
DocType
Critical Node Problem,Node-Exchange Operator,Dynamic Data Structure
Pairwise comparison,Discrete mathematics,Graph,Computer science,Disease control,Heuristics,Degree (graph theory),Operator (computer programming),Local search (optimization),Dynamic data structures,Distributed computing
Conference
ISSN
ISBN
Citations 
2376-5933
978-1-5386-6005-8
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Xiangrong Zeng1105.20
Siyang Liu202.03
LiFan Shen300.34
Yong-Quan Chen443.12
Zhang-Hua Fu5276.49