Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 1 | 47-61
Tytuł artykułu

Embeddings of hamiltonian paths in faulty k-ary 2-cubes

Treść / Zawartość
Warianty tytułu
Języki publikacji
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
  • School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, Peoples Republic of China
  • School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, Peoples Republic of China
  • [1] Y.A. Ashir and I.A. Stewart, Fault-tolerant embeddings of hamiltonian circuits in k-ary n-cubes, SIAM J. Discrete Math. 15 (2002) 317-328, doi: 10.1137/S0895480196311183.
  • [2] S.-Y. Hsieh and Y.-R. Cian, Conditional edge-fault hamiltonicity of augmented cubes, Inform. Sciences 180 (2010) 2596-2617, doi: 10.1016/j.ins.2010.03.005.
  • [3] S.-Y. Hsieh and C.-N. Kuo, Hamilton-connectivity and strongly Hamiltonian-laceability of folded hypercubes, Comput. Math. Appl. 53 (2007) 1040-1044, doi: 10.1016/j.camwa.2006.10.033.
  • [4] S.-Y. Hsieh and C.-W. Lee, Conditional edge-fault hamiltonicity of matching composition networks, IEEE Trans. Parallel Distrib. Syst. 20 (2009) 581-592, doi: 10.1109/TPDS.2008.123.
  • [5] S.-Y. Hsieh and C.-W. Lee, Pancyclicity of restricted hypercube-like networks under the conditional fault model, SIAM J. Discrete Math. 23 (2010) 2100-2119, doi: 10.1137/090753747.
  • [6] S.-Y. Hsieh and C.-D. Wu, Optimal fault-tolerant hamiltonicity of star graphs with conditional edge faults, J. Supercomput. 49 (2009) 354-372, doi: 10.1007/s11227-008-0242-9.
  • [7] T.-L. Kueng, C.-K. Lin, T. Liang, J.J.M. Tan and Lih-Hsing Hsu, Embedding paths of variable lengths into hypercubes with conditional link-faults, Parallel Comput. 35 (2009) 441-454, doi: 10.1016/j.parco.2009.06.002.
  • [8] H.-C. Kim and J.-H. Park Fault hamiltonicity of two-dimensional torus networks, Proceedings of Workshop on Algorithms and Computation WAAC'00, Tokyo, Japan, (2000), 110-117.
  • [9] R.E. Kessler and J.L. Schwarzmeier, Cray T3D: a new dimension for Cray Research, Proceedings of the 38th IEEE Computer Society International Conference, Compcon Spring'93, San Francisco, CA (1993), 176-182.
  • [10] T.-K. Li, C.-H. Tsai, J.J.M. Tan and L.-H. Hsu, Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process. Lett. 87 (2003) 107-110, doi: 10.1016/S0020-0190(03)00258-8.
  • [11] M. Noakes and W.J. Dally, System design of the J-machine, Proceedings of the sixth MIT Conference on Advanced Research in VLSI, (MIT Press, Cambridge, MA, 1990) 179-194.
  • [12] C. Peterson, J. Sutton and P. Wiley, iWarp: a 100-MOPS, LIW microprocessor for multicomputers, IEEE Micro 11(3)(1991) 26-29, 81-87, doi: 10.1109/40.87568.
  • [13] Y. Rouskov, S. Latifi and P.K. Srimani, Conditional fault diameter of star graph networks, J. Parallel Distr. Com. 33 (1996) 91-97, doi: 10.1006/jpdc.1996.0028.
  • [14] L.-M. Shih, J.J.M. Tan and L.-H. Hsu, Edge-bipancyclicity of conditional faulty hypercubes, Inform. Process. Lett. 105 (2007) 20-25, doi: 10.1016/j.ipl.2007.07.009.
  • [15] I.A. Stewart and Y. Xiang, Embedding long paths in k-ary n-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst. 19 (2008) 1071-1085, doi: 10.1109/TPDS.2007.70787.
  • [16] C.-H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theor. Comput. Sci. 314 (2004) 431-443, doi: 10.1016/j.tcs.2004.01.035.
  • [17] S. Wang and S. Lin, Path embeddings in faulty 3-ary n-cubes, Inform. Sciences 180 (2010) 191-197, doi: 10.1016/j.ins.2009.09.007.
  • [18] H.-L. Wang, J.-W. Wang and J.-M. Xu, Edge-fault-tolerant bipanconnectivity of hypercubes, Inform. Sciences 179 (2009) 404-409, doi: 10.1016/j.ins.2008.10.011.
  • [19] M.-C. Yang, J.J.M. Tan and L.-H. Hsu, Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes, J. Parallel Distr. Com. 67 (2007) 362-368, doi: 10.1016/j.jpdc.2005.10.004.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.