Integer programming models and algorithms for the graph decontamination problem with mobile agents
Abstract
This article considers the problem of using synchronous mobile agents to decontaminate the nodes of a graph given a spreading contamination. We begin by considering the problem of minimizing cleaning time, given initial agent, and contamination locations. Then, we take as input a set of all possible locations in which a contamination can start and examine problems in which we strategically preposition agents. In one problem, we minimize the number of agents and prescribe their initial locations, so that the graph can be cleaned within a time limit for any potential initial contamination. We also determine the best initial locations for some predetermined number of agents to minimize expected cleaning time, given probability estimates of potential initial contamination locations. We analyze the complexity of each variant and formulate the problems as mixed‐integer programs. As an alternative method, we also provide a construction heuristic for the cleaning problem and cutting‐plane algorithms for the agent location problems. Computational results using these approaches demonstrate the efficacy of our procedures. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 01, 2012
- Source ID
- 10.1002/net.21460
Entities
People
- J. Cole Smith
- John Penuel
- Siqian Shen
Organizations
- Defense Threat Reduction Agency
- National Science Foundation