Network Decontamination with a Single Agent

详细信息    查看全文

• 作者：Yassine Daadaa ; Asif Jamshed ; Mudassir Shabbir
• 关键词：Network decontamination ; Pursuit ; evasion ; Graph search ; Decontamination with immunity
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：32
• 期：2
• 页码：559-581
• 全文大小：638 KB
• 参考文献：1.Alon, N., Mehrabian, A.: Chasing a fast robber on planar graphs and random graphs. J. Graph Theory (2014)
  2.Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 200–209. ACM (2002)
  3.Bollobás, B., Leader, I.: Compressions and isoperimetric inequalities. J Comb. Theory Ser. A 56(1), 47–62 (1991)CrossRef MATH
  4.Bollobás, B., Leader, I.: Edge-isoperimetric inequalities in the grid. Combinatorica 11(4), 299–314 (1991)CrossRef MathSciNet MATH
  5.Breisch, R.: An intuitive approach to speleotopology. Southwest Cavers 6(5), 72–78 (1967)
  6.Chung, F.: Pebbling in hypercubes. SIAM J. Discrete Math. 2(4), 467–472 (1989)CrossRef MathSciNet MATH
  7.Daadaa, Y.: Network Decontamination with temporal immunity. Ph.D. thesis, University of Ottawa (2012)
  8.Daadaa, Y., Flocchini, P., Zaguia, N.: Network decontamination with temporal immunity by cellular automata. In Cellular Automata, pp. 287–299. Springer (2010)
  9.Daadaa, Y., Flocchini, P., Zaguia, N.: Decontamination with temporal immunity by mobile cellular automata. In International Conference on Scientific Computing (CSC), pp. 172–178 (2011)
  10.Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)CrossRef
  11.Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM J. Algebr. Discrete Methods 3(2), 229–240 (1982)CrossRef MathSciNet MATH
  12.Flocchini, Paola, F.L., Song, L.X.: Size optimal strategies for capturing an intruder in mesh networks. In Proceedings of the International Conference on Communications in Computing (CIC), pp. 200–206, Las Vegas, USA, (2005)
  13.Flocchini, P., Mans, B., Santoro, N.: Tree decontamination with temporary immunity. In Algorithms and Computation, pp. 330–341. Springer (2008)
  14.Kahn, J.: Personal communication (2013)
  15.Kutten, S., Peleg, D.: Fault-local distributed mending. J Algorithms 30(1), 144–165 (1999)CrossRef MathSciNet MATH
  16.Kutten, S., Peleg, D.: Tight fault locality. SIAM J. Comput. 30(1), 247–268 (2000)CrossRef MathSciNet MATH
  17.La Paugh, A.S.: Recontamination does not help to search a graph. J. ACM 40(2), 224–245 (1993)CrossRef
  18.Richard, J.: Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)CrossRef MathSciNet MATH
  19.Luccio, F., Pagli, L., Santoro, N.: Network decontamination with local immunization. In: Proceedings of the 20th International Conference on Parallel and Distributed Processing, pp. 264–264. IEEE Computer Society (2006)
  20.Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The complexity of searching a graph. J ACM 35(1), 18–44 (1988)CrossRef MathSciNet MATH
  21.Parsons, T.D.: Pursuit-evasion in a graph. theory and applications of graphs. Lecture Notes in Mathematics, pp. 426–441. Springer-Verlag (1976)
  22.Parsons, T.D.: The search number of a connected graph. In: Proceedings of the 9th South-Eastern Conference on Combinatorics, Graph Theory, and Computing, pp. 549–554 (1978)
  
• 作者单位：Yassine Daadaa (1)
  Asif Jamshed (1) (2)
  Mudassir Shabbir (3)
  
  1. College of Computer and Information Sciences, Al Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, KSA
  2. PredictifyMe Inc., Raleigh, NC, 27601, USA
  3. Department of Computer Science, Information Technology University, Arfa Technology Park, Lahore, Pakistan
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

Faults and viruses often spread in networked environments by propagating from site to neighboring sites. We model this process of network contamination by graphs. Consider a graph \(G=(V,E)\), whose vertex set is contaminated and our goal is to decontaminate the set \(V\) using mobile decontamination agents that traverse along the edge set of \(G\). Temporal immunity, \(\tau (G) \ge 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\), \(\iota _k(G)\), is the least \(\tau (G)\) 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 \(\iota _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 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.