Integer programming models and algorithms for the graph decontamination problem with mobile agents

John Penuel, J. Cole Smith, Siqian Shen

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-19
Number of pages19
Issue number1
StatePublished - Jan 2013
Externally publishedYes


  • NP-completeness
  • cutting-plane algorithm
  • decomposition
  • graph decontamination
  • integer programming

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Integer programming models and algorithms for the graph decontamination problem with mobile agents'. Together they form a unique fingerprint.

Cite this