2013/07/27 by Yessine Daadaa, Daadaa, Yessine, Asif Jamshed +3
Computer Science · Engineering · Immunology and Microbiology · Mathematics · #Artificial Immune Systems Applications #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #HIV Research and Treatment #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #cs.DM #cs.DS #cs.NI #math.CO
paper · pdf · doi:10.48550/arxiv.1307.7307
arxiv created 2013/07/27 · openalex publication_date 2013/07/27 · arxiv updated 2013/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Faults and viruses often spread in networked environments by propagating from site to neighboring site. We model this process of \em network contamination by graphs. Consider a graph G=(V,E), whose vertex set is contaminated and our goal is to decontaminate the set V(G) using mobile decontamination agents that traverse along the edge set of G. Temporal immunity τ(G) ≥ 0 is defined as the time that a decontaminated vertex of G can remain continuously exposed to some contaminated neighbor without getting infected itself. The immunity number of G, ιk(G), is the least τ that is required to decontaminate G using k agents. We study immunity number for some classes of graphs corresponding to network topologies and present upper bounds on ι1(G), in some cases with matching lower bounds. Variations of this problem have been extensively studied in literature, but proposed algorithms have been restricted to \em monotone strategies, where a vertex, once decontaminated, may not be recontaminated. We exploit nonmonotonicity to give bounds which are strictly better than those derived using monotone strategies.