Tree decontamination with temporary immunity

Paola Flocchini*, Bernard Mans, Nicola Santoro

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

8 Citations (Scopus)


Consider a tree network that has been contaminated by a persistent and active virus: when infected, a network site will continuously attempt to spread the virus to all its neighbours. The decontamination problem is that of disinfecting the entire network using a team of mobile antiviral system agents, called cleaners, avoiding any recontamination of decontaminated areas. A cleaner is able to decontaminate any infected node it visits; once the cleaner departs, the decontaminated node is immune for t∈¥∈0 time units to viral attacks from infected neighbours. After the immunity time t is elapsed, re-contamination can occur. The primary research objective is to determine the minimum team size, as well as the solution strategy, that is the protocol that would enable such a minimal team of cleaners to perform the task. The network decontamination problem has been extensively investigated in the literature, and a very large number of studies exist on the subject. However, all the existing work is limited to the special case t∈=∈0. In this paper we examine the tree decontamination problem for any value t∈¥∈0. We determine the minimum team size necessary to disinfect any given tree with immunity time t. Further we show how to compute for all nodes of the tree the minimum team size and implicitly the solution strategy starting from each starting node; these computations use a total of Θ(n) time (serially) or Θ(n) messages (distributively). We then provide a complete structural characterization of the class of trees that can be decontaminated with k agents and immunity time t; we do so by identifying the forbidden subgraphs and analyzing their properties. Finally, we consider generic decontamination algorithms, i.e. protocols that work unchanged in a large class of trees, with little knowledge of their topological structure. We prove that, for each immunity time t∈¥∈0, all trees of height at most h can be decontaminated by a team of agents whose only knowledge of the tree is the bound h. The proof is constructive.

Original languageEnglish
Title of host publicationAlgorithms and computation
Subtitle of host publication19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 2008, proceedings
EditorsSeok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages12
ISBN (Print)3540921818, 9783540921813
Publication statusPublished - 2008
Event19th International Symposium on Algorithms and Computation, ISAAC 2008 - Gold Coast, QLD, Australia
Duration: 15 Dec 200817 Dec 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5369 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other19th International Symposium on Algorithms and Computation, ISAAC 2008
CityGold Coast, QLD

Fingerprint Dive into the research topics of 'Tree decontamination with temporary immunity'. Together they form a unique fingerprint.

Cite this