The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes

Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying

doi:10.1051/ita/2017008

The connectivity and nature diagnosability of expanded

k

-ary

n

-cubes

Wang, Mujiangshan ¹ ; Lin, Yuqing ¹ ; Wang, Shiying ²

¹ School of Electrical Engineering and Computer Science, The University of Newcastle NSW 2308, Australia.
² School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 2, pp. 71-89.

Résumé

Connectivity and Diagnosability play an important role in measuring the fault tolerance of interconnection networks. As a topology structure of interconnection networks, the expanded $k$ -ary $n$ -cube $X Q^{k}$ $_{n}$ has many good properties. In this paper, we prove that (1) the connectivity of $X Q^{k}$ $_{n}$ is $4 n$ ; (2) the nature connectivity of $X Q^{k}$ $_{n}$ is $8 n - 4$ ; (3) the nature diagnosability of $X Q^{k}$ $_{n}$ under the PMC model and MM $^{*}$ model is $8 n - 3$ for $n \geq 2$ .

MR Zbl

DOI : 10.1051/ita/2017008

Classification : 05C25, 05C90
Mots-clés : Interconnection networks, Combinatorics, Connectivity, Diagnosability, Expandedk-aryn-cubes

Affiliations des auteurs :

Wang, Mujiangshan ¹ ; Lin, Yuqing ¹ ; Wang, Shiying ²

@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita/2017008/

Bibliographie
Cité par

N.R. Adiga, M.A. Blumrich, D. Chen, P. Coteus, A. Gara, M.E. Giampapa, P. Heidelberger, S. Singh, B.D. Steinmacher−Burow, T. Takken, M. Tsao and P. Vranas, Blue Gene/L torus interconnection network. IBM J. Res. Dev. 49 (2005) 265–276. | DOI

F. Barsi, F. Grandoni and P. Maestrini, A theory of diagnosability of digital systems. IEEE Trans. Comput. 25 (1976) 585–593. | DOI | MR | Zbl

J.A. Bondy and U.S.R. Murty, Graph Theory. Springer, New York (2007). | MR | Zbl

Bella Bose, Bob Broeg, Younggeun Kwon and Yaagoub Ashir, Lee distance and topological properties of k-ary $n$ -cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. | DOI | MR | Zbl

Nai-Wen Chang and Sun−Yuan Hsieh, Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst. 25 (2014) 3002–3011. | DOI

A.T. Dahbura and G.M. Masson, An $O (n^{2.5})$ fault identification algorithm for diagnosable systems, IEEE Trans. Comput. 33 (1984) 486–492. | DOI | Zbl

Kh. Day and A.-E. Al-Ayyoub and F. diameter of $k$ -ary $n$ -cube networks. IEEE Trans. Parallel and Distrib. Syst. 8 (1997) 903–907. | DOI

J. Fan, Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans. Parallel Distrib. Syst. 13 (2002) 1099–1104. | DOI

Y. Hao and Shiying Wang, The 1-good-neighbor diagnosibility of augmented $k$ -ary $n$ -cubes. Adv. Appl. Math. 5 (2016) 762–772. | DOI

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.

P.-Lien Lai, J.M. Tan, Ch.-P. Chang and Lih−Hsing Hsu, Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54 (2005) 165–175. | DOI

Cheng−Kuan Lin, Jimmy J.M. Tan, Lih−Hsing Hsu, 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

Shao−Lun Peng, Cheng−Kuan Lin, Ji.J.M. Tan and Lih−Hsing Hsu, The g-good-neighbor conditional diagnosability of hypercube under PMC model. Appl. Math. Comput. 218 (2012) 10406–10412. | MR | Zbl

C. Peterson, J. Sutton and P. Wiley, iWarp: a 100-MOPS VLIW microprocessor for multicomputers. IEEE Micro 11 (1991) 26–37. | DOI

F.P. Preparata, G. Metze and R.T. Chien, On the connection assignment problem of diagnosable systems. IEEE Trans. Comput. EC-16 (1967) 848–854. | DOI | Zbl

Mujiangshan Wang, Yubao Guo and Shiying Wang, 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

Mujiangshan Wang, Yuqing Lin and Shiying Wang, 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

Shiying Wang and Weiping Han, The $g$ -good-neighbor conditional diagnosability of $n$ -dimensional hypercubes under the MM* model. Inf. Process. Lett. 116 (2016) 574–577. | DOI | MR | Zbl

Shiying Wang, Zhenhua Wang and Mujiangshan Wang, The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks. Comput. J. 59 (2016) 1839–1856. | DOI | MR

Shiying Wang, Zhenhua Wang and Mujiangshan Wang, 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

Shiying Wang and Yuxing Yang, 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

Yonghong Xiang and Iain A. Stewart, Augmented $k$ -ary $n$ -cubes. Inf. Sci. 181 (2011) 239–256. | DOI | MR | Zbl

Jun Yuan, Aixia Liu, Xue Ma, Xiuli Liu, Xiao Qin and Jifu Zhang, The $g$ -good-neighbor conditional diagnosability of $k$ -ary $n$ -cubes under the PMC model and MM $^{*}$ model. IEEE Trans. Parallel Distrib. Syst. 26 (2015) 1165–1177. | DOI

Jun Yuan, Aixia Liu, Xiao Qin, Jifu Zhang and Jing Li, $g$ -Good-neighbor conditional diagnosability measures for 3-ary $n$ -cube networks. Theoret. Comput. Sci. 622 (2016) 144–162. | DOI | MR | Zbl

Shurong Zhang and Weihua Yang, The g-extra conditional diagnosability and sequential $t / k$ -diagnosability of hypercubes. Inter. J. Comput. Math. 93 (2016) 482–497. | DOI | MR | Zbl

Nan Zhao and Shiying Wang, The 1-good-neighbor diagnosability of augmented 3-ary $n$ -cubes. Adv. Appl. Math. 5 (2016) 754–761. | DOI

Cité par Sources :