EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Interdiction Models and Heuristics for Graph Propagation

Agostinho Agra, José Maria Samuco

Networks · 14.05.2026

DOI: 10.1002/net.70047 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 14.05.2026. Verfasst von Agostinho Agra und 1 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundação para a Ciência e a Tecnologia.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a graph and a set of activated/infected nodes, we consider the problem of determining the set of nodes that minimizes the network propagation on the subgraph that results from the removal of those nodes. To measure network propagation, we assume that a node is activated/infected in the resulting subgraph if there is a path from an activated/infected node in to node . Several mixed‐integer programs are presented to find the critical nodes to prevent propagation on directed and undirected graphs. Two compact models are devised by adapting the best‐known models for determining a set of critical nodes in a graph to this problem. A new compact model is devised from a network interdiction formulation, and a new path‐formulation model is introduced. We show that all the models provide the same linear relaxation bound and compare them on a set of instances from the literature. To address the computational challenges of large networks, several efficient heuristics are introduced. The results show that the compact model from the interdiction perspective is faster, allowing it to solve to optimality sparse networks with up to 10 000 nodes.

Förderung

  • Fundação para a Ciência e a Tecnologia

Zitieren

APA

Agra, A., & Samuco, J. M. (2026). Interdiction Models and Heuristics for Graph Propagation. Networks. https://doi.org/10.1002/net.70047

Vancouver

Agra A, Samuco JM. Interdiction Models and Heuristics for Graph Propagation. Networks. 2026. doi:10.1002/net.70047

BibTeX
@article{Agra2026,
  author = {Agra, Agostinho and Samuco, José Maria},
  title = {Interdiction Models and Heuristics for Graph Propagation},
  journal = {Networks},
  year = {2026},
  doi = {10.1002/net.70047}
}
Kostenlos starten →