A. Agra, J. M. Samuco
Given a graph G=(N,E) and a set S of activated/infected nodes (S subset of N), we consider the problem of determining the set of c nodes that minimizes the network propagation on the subgraph that results from the removal of those c nodes. To measure the network propagation, we assume that node i becomes activated/infected in the subgraph resulting from removing c nodes, that is, if there is a path from a source node in S to node i. Several mixed integer programs are presented to find the critical nodes to prevent propagation on directed and undirected graphs. Two models are devised by adapting the best-known models for determining a set of critical nodes in a graph to this problem. A new model is developed from a network interdiction formulation. The models are compared on a set of instances from the literature. The results show that the proposed models are much faster, allowing us to find the best solution for networks with up to 10,000 nodes that are directed in less than 10 seconds
Palabras clave: critical nodes, graph propagation, connectivity, mixed integer linear programming, interdiction network.
Programado
Optimización Entera y Combinatoria
10 de junio de 2025 17:10
MR 3