We consider the monotone connected graph search problem, that is, the problem of decontaminating a network infected by a mobile virus, using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex v, this vertex will become recontaminated if m or more of its neighbours are infected, where m 1 is a threshold parameter of the system. In the literature,the value of m has been limited to m = 1 or to the strict majority of the neighbours of the nodes. In this paper, we consider this problem for any integer value m 1. Wedirect our investigation to widely used interconnection networks, namely meshes, hypercubes, and trees. For each of these classes of networks, we establish matching upper and lower bounds on the number of agents necessary to decontaminate with threshold m. The upper bound proofs are constructive: we present optimal decontamination protocols; we alsoshow that these protocols are optimal or near-optimal in terms of number of moves.

Optimal Network Decontamination with Threshold Immunity

LUCCIO, FABRIZIO;PAGLI, LINDA;
2013

Abstract

We consider the monotone connected graph search problem, that is, the problem of decontaminating a network infected by a mobile virus, using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex v, this vertex will become recontaminated if m or more of its neighbours are infected, where m 1 is a threshold parameter of the system. In the literature,the value of m has been limited to m = 1 or to the strict majority of the neighbours of the nodes. In this paper, we consider this problem for any integer value m 1. Wedirect our investigation to widely used interconnection networks, namely meshes, hypercubes, and trees. For each of these classes of networks, we establish matching upper and lower bounds on the number of agents necessary to decontaminate with threshold m. The upper bound proofs are constructive: we present optimal decontamination protocols; we alsoshow that these protocols are optimal or near-optimal in terms of number of moves.
9783642382321
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/229338
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact