INTRUDER CAPTURING IN MESH AND TORUS NETWORKS

作者: N. IMANI , H. SARBAZI-AZAD , A. ZOMAYA

DOI: 10.1142/S0129054108006121

关键词: TorusSpherical waveOn demandComputer scienceDistributed computingMultiprocessor interconnectionTraverseSingle agent

摘要: In this paper, we propose a solution for the problem of capturing an intruder in two popular interconnection topologies namely, mesh and torus. A set agents collaborate to capture hostile network. While can move network one hop at time, is assumed be arbitrarily fast i.e. it traverse any number nodes contiguously as far there are no those nodes. Here consider new version where each agent replicate when needed, algorithm starts with single created on demand. We define class algorithms intruder. particular, different torus networks will later discuss about merits based some performance criteria.

参考文章(5)
C. Y. Tang, M.-T. Ko, C.-W. Ho, T.-s. Hsu, S.-L. Peng, Graph Searching on Some Subclasses of Chordal Graphs Algorithmica. ,vol. 27, pp. 395- 426 ,(2000) , 10.1007/S004530010026
Andrea S. LaPaugh, Recontamination does not help to search a graph Journal of the ACM. ,vol. 40, pp. 224- 245 ,(1993) , 10.1145/151261.151263
Lefteris M. Kirousis, Christos H. Papadimitriou, Searching and pebbling Theoretical Computer Science. ,vol. 47, pp. 205- 218 ,(1986) , 10.1016/0304-3975(86)90146-5
J.A. Ellis, I.H. Sudborough, J.S. Turner, The vertex separation and search number of a graph Information & Computation. ,vol. 113, pp. 50- 79 ,(1994) , 10.1006/INCO.1994.1064
N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, C. H. Papadimitriou, The complexity of searching a graph Journal of the ACM. ,vol. 35, pp. 18- 44 ,(1988) , 10.1145/42267.42268