Network decontamination under -immunity

详细信息    查看全文

• 作者：Paola Flocchini^a ; ^{flocchin@site.uottawa.ca" class="auth_mail" title="E-mail the corresponding author} ; Fabrizio Luccio^b ; ^{luccio@di.unipi.it" class="auth_mail" title="E-mail the corresponding author} ; Linda Pagli^b ; ^{pagli@di.unipi.it" class="auth_mail" title="E-mail the corresponding author} ; Nicola Santoro^c ; ^{santoro@scs.carleton.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Network decontamination ; Connected graph search ; Monotone algorithms ; Immunity ; Meshes ; Tori ; Trees
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 March 2016
• 年：2016
• 卷：201
• 期：Complete
• 页码：114-129
• 全文大小：815 K

文摘

We consider the problem of decontaminating an infected network using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si56.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=cdd0871bfb6150b0f4e4ffe8337688bb" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$, this vertex will become recontaminated if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si60.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=e5cd44ce8abb429003339a42bb882465" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$ or more of its neighbors are infected, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si63.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=0a24872bfb1dedb40657327214e2fadd" title="Click to view the MathML source">m≥1class="mathContainer hidden">class="mathCode">$m\ge 1$ is a threshold parameter of the system indicating the local immunity level of the network. This network decontamination problem, also called monotone connected graph search and intruder capture  , has been extensively studied in the literature when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si1.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=ac9d4acd22817177a8efaf3d28b7ecb6" title="Click to view the MathML source">m=1class="mathContainer hidden">class="mathCode">$m=1$ (no immunity).

In this paper, we extend these investigations and consider for the first time the network decontamination problem when the parameter class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si60.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=e5cd44ce8abb429003339a42bb882465" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$ is an arbitrary integer value class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si63.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=0a24872bfb1dedb40657327214e2fadd" title="Click to view the MathML source">m≥1class="mathContainer hidden">class="mathCode">$m\ge 1$. We direct our study to widely used interconnection networks, namely meshes, tori, and trees. For each of these classes of networks, we present decontamination algorithms with threshold class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si60.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=e5cd44ce8abb429003339a42bb882465" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$; these algorithms work even in asynchronous setting, either directly or with a simple modification requiring one additional agent. We also establish general lower bounds on the number of agents necessary for decontamination with immunity class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X1500373X&_mathId=si60.gif&_user=111111111&_pii=S0166218X1500373X&_rdoc=1&_issn=0166218X&md5=e5cd44ce8abb429003339a42bb882465" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$; these bounds are tight in the case of trees, while large gaps still exist in the case of meshes and tori.