TY - GEN
T1 - Tree decontamination with temporary immunity
AU - Flocchini, Paola
AU - Mans, Bernard
AU - Santoro, Nicola
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58549094763&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-92182-0_31
DO - 10.1007/978-3-540-92182-0_31
M3 - Conference proceeding contribution
AN - SCOPUS:58549094763
SN - 3540921818
SN - 9783540921813
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 330
EP - 341
BT - Algorithms and computation
A2 - Hong, Seok-Hee
A2 - Nagamochi, Hiroshi
A2 - Fukunaga, Takuro
PB - Springer, Springer Nature
CY - Berlin
T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008
Y2 - 15 December 2008 through 17 December 2008
ER -