A derandomized approximation algorithm for the critical node detection problem |
| |
| Affiliation: | 1. Department of Computer Science and Artificial Intelligence, University of Granada, Granada, Spain;2. Computing and Numerical Analysis Department, University of Córdoba, Córdoba, Spain;3. Department of Computer Science, University of Extremadura, Mérida, Spain;4. Department of Methodology of Behavioral Sciences, University of Granada, Granada, Spain;1. Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China;2. Sino-US Global Logistics Institute, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China;3. Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China;4. Department of Computer Science, Université d’Angers, Angers 49045, France |
| |
| Abstract: | In this paper we propose an efficient approximation algorithm for determining solutions to the critical node detection problem (CNDP) on unweighted and undirected graphs. Given a user-defined number of vertices , the problem is to determine which k nodes to remove such as to minimize pairwise connectivity in the induced subgraph. We present a simple, yet powerful, algorithm that is derived from a randomized rounding of the relaxed linear programming solution to the CNDP. We prove that the expected solution quality obtained by the linear-time algorithm is bounded by a constant. To highlight the algorithm quality four common complex network models are utilized, in addition to four real-world networks. |
| |
| Keywords: | Critical node detection problem Randomized rounding Complex network |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
