Document Type : Research Paper


1 Department of Algorithms and Computation, University of Tehran.

2 University of Tehran, College of Engineering, Faculty of Engineering Science


In this paper, we present a binary-linear optimization model to prevent the spread of an infectious disease in a community. The model is based on the remotion of some connections in a contact network in order to separate infected nodes from the others. By using this model we nd an exact optimal solution and determine not only the minimum number of deleted links but also their exact positions. The formulation of the model is insensitive to the number of edges in a graph and can be used (with complete or local information) to measure the resistance of a network before and after an infectious spreads. Also, we propose some related models as generalizations: quarantining problem including resource constraints (time, budget, etc.), maximum rescued nodes-minimum deleted links problem and minimum removed links problem nding a prespeci ed number of nodes with weakest connections.