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

Shiying Wang; Shurong Zhang

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 47-61
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Shiying Wang, and Shurong Zhang. "Embeddings of hamiltonian paths in faulty k-ary 2-cubes." Discussiones Mathematicae Graph Theory 32.1 (2012): 47-61. <http://eudml.org/doc/270809>.

@article{ShiyingWang2012,
abstract = {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.},
author = {Shiying Wang, Shurong Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {complex networks; path embeddings; fault-tolerance; k-ary n-cubes; -ary -cubes},
language = {eng},
number = {1},
pages = {47-61},
title = {Embeddings of hamiltonian paths in faulty k-ary 2-cubes},
url = {http://eudml.org/doc/270809},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Shiying Wang
AU - Shurong Zhang
TI - Embeddings of hamiltonian paths in faulty k-ary 2-cubes
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 47
EP - 61
AB - 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.
LA - eng
KW - complex networks; path embeddings; fault-tolerance; k-ary n-cubes; -ary -cubes
UR - http://eudml.org/doc/270809
ER -

References

top
  1. [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. [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. Zbl1209.68375
  3. [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. Zbl1149.68409
  4. [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. [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. Zbl1207.05106
  6. [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. [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. [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. [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. [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. Zbl1161.68684
  11. [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. [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. [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. [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. Zbl1185.05091
  15. [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. [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. Zbl1072.68082
  17. [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. Zbl1183.68093
  18. [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. Zbl1163.68314
  19. [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. Zbl1115.68032

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.