Efficient methods for the distance-based critical node detection problem in complex networks

DOI10.1016/j.cor.2021.105254OpenAlexW3131340246MaRDI QIDQ2668688

Kerem Akartunalı, Glory Uche Alozie, Ashwin Arulselvan, Eduardo L. Pasiliao

Publication date: 7 March 2022

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2021.105254

zbMATH Keywords

integer programmingcritical node problembreadth first searchdistance connectivitylazy constraints

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items

Solving the Distance-Based Critical Node Problem, Integer programming methods for solving binary interdiction games, A fast tri-individual memetic search approach for the distance-based critical node problem

Uses Software

• NetworkX
• GraphBase
• Pajek
• Gurobi
• Pajek datasets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying sets of key players in a social network
• Hybrid constructive heuristics for the critical node problem
• Information theory perspective on network robustness
• Methods for removing links in a network to minimize the spread of infections
• An integer programming framework for critical elements detection in graphs
• Complexity of the critical node problem over trees
• Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
• Detecting critical nodes in sparse graphs
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• Branch-and-cut methods for the network design problem with vulnerability constraints
• Design of survivable networks with vulnerability constraints
• Efficiency of scale-free networks: Error and attack tolerance
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Exact identification of critical nodes in sparse networks via new compact formulations
• Cardinality-Constrained Critical Node Detection Problem
• Emergence of Scaling in Random Networks
• Community structure in social and biological networks
• Centrality Analysis for Modified Lattices
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Hop‐level flow formulation for the survivable network design with hop constraints problem