Connectivity and Diagnosability play an important role in measuring the fault tolerance of interconnection networks. As a topology structure of interconnection networks, the expanded -ary -cube has many good properties. In this paper, we prove that (1) the connectivity of is ; (2) the nature connectivity of is ; (3) the nature diagnosability of under the PMC model and MM model is for .
Mots-clés : Interconnection networks, Combinatorics, Connectivity, Diagnosability, Expandedk-aryn-cubes
@article{ITA_2017__51_2_71_0, author = {Wang, Mujiangshan and Lin, Yuqing and Wang, Shiying}, title = {The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {71--89}, publisher = {EDP-Sciences}, volume = {51}, number = {2}, year = {2017}, doi = {10.1051/ita/2017008}, mrnumber = {3731538}, zbl = {1379.05056}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2017008/} }
TY - JOUR AU - Wang, Mujiangshan AU - Lin, Yuqing AU - Wang, Shiying TI - The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2017 SP - 71 EP - 89 VL - 51 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2017008/ DO - 10.1051/ita/2017008 LA - en ID - ITA_2017__51_2_71_0 ER -
%0 Journal Article %A Wang, Mujiangshan %A Lin, Yuqing %A Wang, Shiying %T The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2017 %P 71-89 %V 51 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2017008/ %R 10.1051/ita/2017008 %G en %F ITA_2017__51_2_71_0
Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying. The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 2, pp. 71-89. doi : 10.1051/ita/2017008. http://archive.numdam.org/articles/10.1051/ita/2017008/
Blue Gene/L torus interconnection network. IBM J. Res. Dev. 49 (2005) 265–276. | DOI
, , , , , , , , , , and ,A theory of diagnosability of digital systems. IEEE Trans. Comput. 25 (1976) 585–593. | DOI | MR | Zbl
, and ,J.A. Bondy and U.S.R. Murty, Graph Theory. Springer, New York (2007). | MR | Zbl
Lee distance and topological properties of k-ary -cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. | DOI | MR | Zbl
, , and ,Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst. 25 (2014) 3002–3011. | DOI
and ,An fault identification algorithm for diagnosable systems, IEEE Trans. Comput. 33 (1984) 486–492. | DOI | Zbl
and ,F. diameter of -ary -cube networks. IEEE Trans. Parallel and Distrib. Syst. 8 (1997) 903–907. | DOI
and andDiagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans. Parallel Distrib. Syst. 13 (2002) 1099–1104. | DOI
,The 1-good-neighbor diagnosibility of augmented -ary -cubes. Adv. Appl. Math. 5 (2016) 762–772. | DOI
and ,Th.W. Hungerford, Algebra. Springer-Verlag, New York (1974). | MR | Zbl
R.E. Kessler and J.L. Schwarzmeier, Cray T3D: a new dimension for Cray research, in Proc. 38th IEEE Comput. Soc. Inter. Confer., Spring, San Francisco (1993) 176–182.
Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54 (2005) 165–175. | DOI
, , and ,Eddie Cheng and László Lipták, Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J. Interconnection Netw. 9 (2008) 83–97. | DOI
, , ,J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessor systems, in Proc. 11th Inter. Symp. Fault-Tolerant Comput. (1981) 173–175.
M. Noakes and W.J. Dally, System design of the J-machine, in: Proceedings of the sixth MIT conference on Advanced research in VLSI. MIT Press, Cambridge (1990) 179–194. | MR
The g-good-neighbor conditional diagnosability of hypercube under PMC model. Appl. Math. Comput. 218 (2012) 10406–10412. | MR | Zbl
, , and ,iWarp: a 100-MOPS VLIW microprocessor for multicomputers. IEEE Micro 11 (1991) 26–37. | DOI
, and ,On the connection assignment problem of diagnosable systems. IEEE Trans. Comput. EC-16 (1967) 848–854. | DOI | Zbl
, and ,The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM model. Int. J. Comput. Math. 94 (2017) 620–631. | DOI | MR | Zbl
, and ,The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Theoret. Comput. Sci. 628 (2016) 92–100. | DOI | MR | Zbl
, and ,The -good-neighbor conditional diagnosability of -dimensional hypercubes under the MM* model. Inf. Process. Lett. 116 (2016) 574–577. | DOI | MR | Zbl
and ,The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks. Comput. J. 59 (2016) 1839–1856. | DOI | MR
, and ,The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks. Discrete Appl. Math. 217 (2017) 691–706. | DOI | MR | Zbl
, and ,The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model. Appl. Math. Comput. 305 (2017) 241–250. | MR | Zbl
and ,Augmented -ary -cubes. Inf. Sci. 181 (2011) 239–256. | DOI | MR | Zbl
and ,The -good-neighbor conditional diagnosability of -ary -cubes under the PMC model and MM model. IEEE Trans. Parallel Distrib. Syst. 26 (2015) 1165–1177. | DOI
, , , , and ,-Good-neighbor conditional diagnosability measures for 3-ary -cube networks. Theoret. Comput. Sci. 622 (2016) 144–162. | DOI | MR | Zbl
, , , and ,The g-extra conditional diagnosability and sequential -diagnosability of hypercubes. Inter. J. Comput. Math. 93 (2016) 482–497. | DOI | MR | Zbl
and ,The 1-good-neighbor diagnosability of augmented 3-ary -cubes. Adv. Appl. Math. 5 (2016) 754–761. | DOI
and ,Cité par Sources :