Paths and cycles identifying vertices in twisted cubes

被引：3
作者：
Lai, Pao-Lien [1 ]
机构：
[1] Natl Dong Hwa Univ, Dept Comp Sci & Informat Engn, Shoufeng 97401, Hualien, Taiwan
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2015年 / 259卷
关键词：
Identify; Fault diagnosis; Gray code; Twisted cubes; Path; Cycle; GENERALIZED GRAY CODES; HAMILTONIAN CYCLES; CROSSED CUBE; EDGE; MULTIPROCESSORS; IDENTIFICATION; SIMULATION; FAMILIES; LATTICE; GRAPHS;
D O I：
10.1016/j.amc.2015.02.090
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is an important variation of the hypercube and preserves many of its desirable properties. Karpovsky et al. introduced the concept of identifying codes to model fault-detection in multiprocessor systems and Honkala et al. developed an identifying code by using cycles to identify the faulty processors in the hypercube. In this paper, we study the vertex identification problem on the twisted cube. We first propose an interesting construction scheme to build paths and cycles, and furthermore apply a minimum number of paths and cycles to identify the faulty processors of the twisted cube. (C) 2015 Elsevier Inc. All rights reserved.
引用
收藏
页码：620 / 627
页数：8
相关论文
共 39 条
  • [11] A lower bound on the number of Hamiltonian cycles through a prescribed edge in a crossed cube
    Chen, Jheng-Cheng
    Lai, Chia-Jui
    Tsai, Chang-Hsiung
    Lai, Pao-Lien
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2013, 219 (19) : 9885 - 9892
  • [12] PROCESSOR ALLOCATION IN AN N-CUBE MULTIPROCESSOR USING GRAY CODES
    CHEN, MS
    SHIN, KG
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (12) : 1396 - 1407
  • [13] Bounds for codes identifying vertices in the hexagonal grid
    Cohen, GD
    Honkala, I
    Lobstein, A
    Zémor, G
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (04) : 492 - 504
  • [14] On codes identifying vertices in the two-dimensional square lattice with diagonals
    Cohen, GD
    Honkala, I
    Lobstein, A
    Zémor, G
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (02) : 174 - 176
  • [15] Embedding of cycles in twisted cubes with edge-pancyclic
    Fan, Jianxi
    Jia, Xiaohua
    Lin, Xiaola
    [J]. ALGORITHMICA, 2008, 51 (03) : 264 - 282
  • [16] An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges
    Fan, Jianxi
    Jia, Xiaohua
    Cheng, Baolei
    Yu, Jia
    [J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) : 3440 - 3450
  • [17] Efficient unicast in bijective connection networks with the restricted faulty node set
    Fan, Jianxi
    Jia, Xiaohua
    Liu, Xin
    Zhang, Shukui
    Yu, Jia
    [J]. INFORMATION SCIENCES, 2011, 181 (11) : 2303 - 2315
  • [18] Fan JX, 2005, LECT NOTES COMPUT SC, V3827, P1090
  • [19] Fault-free Hamiltonian cycles in twisted cubes with conditional link faults
    Fu, Jung-Sheng
    [J]. THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) : 318 - 329
  • [20] Hilbers P.A.J., 1987, PARALLEL ARCHITECTUR, V1, P152
1234