Geodesic
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 47-61.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: complex networks, path embeddings, fault-tolerance, k-ary n-cubes 
@article{DMGT_2012_32_1_a4,
     author = {Wang, Shiying and Zhang, Shurong},
     title = {Embeddings of hamiltonian paths in faulty k-ary 2-cubes},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {47--61},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a4/}
}
TY  - JOUR
AU  - Wang, Shiying
AU  - Zhang, Shurong
TI  - Embeddings of hamiltonian paths in faulty k-ary 2-cubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 47
EP  - 61
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a4/
LA  - en
ID  - DMGT_2012_32_1_a4
ER  - 
%0 Journal Article
%A Wang, Shiying
%A Zhang, Shurong
%T Embeddings of hamiltonian paths in faulty k-ary 2-cubes
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 47-61
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a4/
%G en
%F DMGT_2012_32_1_a4
Wang, Shiying; Zhang, Shurong. Embeddings of hamiltonian paths in faulty k-ary 2-cubes. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 47-61. http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a4/

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