平衡立方体的h-额外连通度及h-额外条件诊断数
|
摘要
互连网络的连通度和可诊断数是衡量网络性能优劣的经典参数.h-额外连通度作为连通度的一种推广,是度量互连网络可靠性的一个重要指标.相应地,h-额外条件诊断数作为传统可诊断度的推广,也是度量系统诊断能力的一种新的性能指标.另外,平衡立方体网络作为超立方体网络的变形,在保留前者原有优良性能的基础上,又增加了一些新的优良性能.文中确定了平衡立方体(BH_n)的4-额外连通度和5-额外连通度都是6n-8.在此基础上,进一步推导出当h=4,5,n≥4时,BH_n在PMC模型下的h-额外条件可诊断数是6n-3.从而表明了在h-额外条件诊断策略下的可诊断数几乎是传统可诊断数的3倍.
Connectivity and diagnosiability of interconnection networks are classic parameters to evaluate the performance of interconnection networks. As a generalization of connectivity, the h-extra connectivity is an important measure for the reliability of interconnection networks. Similarly, the hextra conditional diagnosability, as a generalization of diagnosability, can better measure the diagnosis capability of interconnection networks. In addition, As a kind of variant of hypercube, balanced hypercube preserves the advantages of hypercube and gives better performances. In this paper, the4, 5-extra connectivity of balanced hypercube(BH_n) are studied, the results are shown as 6 n-8. And on this basis, the h-extra conditional diagnosability of BHn under the PMC model is determined to be6 n-3 for h = 4, 5,n ≥4, which is about three times as large as the classical diagnosability.
Connectivity and diagnosiability of interconnection networks are classic parameters to evaluate the performance of interconnection networks. As a generalization of connectivity, the h-extra connectivity is an important measure for the reliability of interconnection networks. Similarly, the hextra conditional diagnosability, as a generalization of diagnosability, can better measure the diagnosis capability of interconnection networks. In addition, As a kind of variant of hypercube, balanced hypercube preserves the advantages of hypercube and gives better performances. In this paper, the4, 5-extra connectivity of balanced hypercube(BH_n) are studied, the results are shown as 6 n-8. And on this basis, the h-extra conditional diagnosability of BHn under the PMC model is determined to be6 n-3 for h = 4, 5,n ≥4, which is about three times as large as the classical diagnosability.
引文
[1] Harary F. Conditional connectivity[J]. Networks, 1983, 13(3):347-357.
[2] Chen YChuang, Tan Jimmy J. M, Hsu LihHsing, et al. Super-connectivity and super-edgeconnectivity for some interconnection networks[J]. Applied Mathematics and Computation,2003, 140(2-3):245-254.
[3] Ma Meijie, Liu Guizhen, Xu JunMing. The super connectivity of augmented cubes[J]. Information Processing Letters, 2008, 106(2):59-63.
[4] Ma MeiJie. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011, 111(8):360-364.
[5] Xu Junming,LüMin,Ma Meijie, et al. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94(4):191-195.
[6] Boesch F, Tindell R. Circulants and their connectivities[J]. Journal of Graph Theory, 2010,8(4):487-499.
[7] Wan Min, Zhang Zhao. A kind of conditional vertex connectivity of star graphs[J]. Applied Mathematics Letters, 2009, 22(2):264-267.
[8] Fabrega J, Fiol M A. Extra connectivity of graphs with large girth[J]. Discrete Mathematics,1994, 127(1-3):163-170.
[9] Chang N W, Tsai C Y, Hsieh S Y. On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes[J]. IEEE Transactions on Computers, 2014, 63(6):1594-1600.
[10] Guo Jia, Lu Mei. The extra connectivity of bubble-sort star graphs[J]. Theoretical Computer Science, 2016, 645:91-99.
[11] Lin Limei, Zhou Shuming, Xu Li, et al. The extra connectivity and conditional diagnosability of alternating group networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015, 26(8):2352-2362.
[12] Xu Li, Lin Limei, Zhou Shuming, et al. The extra connectivity, extra conditional diagnosability, and, t/m-diagnosability of arrangement graphs[J]. IEEE Transactions on Reliability,2016, 65(3):1248-1262.
[13] Zhang Mimi, Zhou Jinxin. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015, 593:146-153.
[14] Zhu Qiang, Wang Xinke, Cheng Guanglan. Reliability evaluation of BC networks[J]. IEEE Transactions on Computers, 2013, 62(11):2337-2340.
[15] Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers, 1966, EC-16(6):848-854.
[16] Chang N W, Hsieh S Y. Structural properties and conditional diagnosability of star graphs by using the PMC model[J]. IEEE Transactions on Parallel and Distributed Systems, 2014,25(11):3002-3011.
[17] Hao Rongxia, Gu Meimei, Feng Yanquan. The pessimistic diagnosabilities of some general regular graphs[M]. Theoretical Computer Science, Elsevier Science Publishers Ltd. 2016,609(P2):413-420.
[18] Lai Paolien, Tan Jimmy J M, Chang Chienping, et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005, 54(2):165-175.
[19] Peng Shaolun, Lin Chengkuan, Tan Jimmy J M, et al. The g-good-neighbor conditional diagnosability of hypercube under PMC model[J]. Applied Mathematics and Computation,2012, 218(21):10406-10412.
[20] Yang Weihua, Lin Huiqiu, Qin Chengfu. On the t/k-diagnosability of BC networks[J]. Applied Mathematics and Computation, 2013, 225(12):366-371.
[21] Yuan Jun, Liu Aixia, Ma Xue, et al. The g-good-neighbor conditional diagnosability of kAry n-Cubes under the PMC model and MM*model[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 26(4):1165-1177.
[22] Zhu Qiang, Guo Guodong, Tang Wenliang, et al. A diagnosis algorithm by using graphcoloring under the PMC model[J]. Journal of Combinatorial Optimization, 2016, 32(3):960-969.
[23] Zhang Shurong, Yang Weihua. The g-extra conditional diagnosability and sequential t/kdiagnosability of hypercubes[J]. International Journal of Computer Mathematics, Taylor and Francis, 2016, 93(3):16.
[24] Wu Jie, Huang Ke. The balanced hypercube:a cube-based system for fault-tolerant applications[J]. IEEE Transactions on Computers, 1997, 46(4):484-490.
[25] Yang Mingchien. Bipanconnectivity of balanced hypercubes[J]. Computers and Mathematics with Applications, 2010, 60(7):1859-1867.
[26] Yang Mingchien. Super connectivity of balanced hypercubes[J]. Applied Mathematics and Computation, 2012, 219(3):970-975.
[27] Yang Mingchien, Yang Minghour. Reliability analysis of balanced hypercubes[A]. Computing, Communications and Applications Conference[C]. IEEE, 2012, 376-379.
[28] Lii Huazhong. On extra connectivity and extra edge-connectivity of balanced hypercubes[J].International Journal of Computer Mathematics, 2017, 94(4):8.
[29] Dahbura Anton T, Masson Gerald M. An O(n~(2.5))fault identification algorithm for diagnosable systems[J]. IEEE Computer Society, 1984, 100(6):486-492.
[30] Zhou Jinxin, Wu Zhenlin, Yang Shichen, et al. Symmetric property and reliability of balanced hypercube[J]. IEEE Transactions on Computers, 2015, 64(3):876-881.
[2] Chen YChuang, Tan Jimmy J. M, Hsu LihHsing, et al. Super-connectivity and super-edgeconnectivity for some interconnection networks[J]. Applied Mathematics and Computation,2003, 140(2-3):245-254.
[3] Ma Meijie, Liu Guizhen, Xu JunMing. The super connectivity of augmented cubes[J]. Information Processing Letters, 2008, 106(2):59-63.
[4] Ma MeiJie. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011, 111(8):360-364.
[5] Xu Junming,LüMin,Ma Meijie, et al. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94(4):191-195.
[6] Boesch F, Tindell R. Circulants and their connectivities[J]. Journal of Graph Theory, 2010,8(4):487-499.
[7] Wan Min, Zhang Zhao. A kind of conditional vertex connectivity of star graphs[J]. Applied Mathematics Letters, 2009, 22(2):264-267.
[8] Fabrega J, Fiol M A. Extra connectivity of graphs with large girth[J]. Discrete Mathematics,1994, 127(1-3):163-170.
[9] Chang N W, Tsai C Y, Hsieh S Y. On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes[J]. IEEE Transactions on Computers, 2014, 63(6):1594-1600.
[10] Guo Jia, Lu Mei. The extra connectivity of bubble-sort star graphs[J]. Theoretical Computer Science, 2016, 645:91-99.
[11] Lin Limei, Zhou Shuming, Xu Li, et al. The extra connectivity and conditional diagnosability of alternating group networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015, 26(8):2352-2362.
[12] Xu Li, Lin Limei, Zhou Shuming, et al. The extra connectivity, extra conditional diagnosability, and, t/m-diagnosability of arrangement graphs[J]. IEEE Transactions on Reliability,2016, 65(3):1248-1262.
[13] Zhang Mimi, Zhou Jinxin. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015, 593:146-153.
[14] Zhu Qiang, Wang Xinke, Cheng Guanglan. Reliability evaluation of BC networks[J]. IEEE Transactions on Computers, 2013, 62(11):2337-2340.
[15] Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers, 1966, EC-16(6):848-854.
[16] Chang N W, Hsieh S Y. Structural properties and conditional diagnosability of star graphs by using the PMC model[J]. IEEE Transactions on Parallel and Distributed Systems, 2014,25(11):3002-3011.
[17] Hao Rongxia, Gu Meimei, Feng Yanquan. The pessimistic diagnosabilities of some general regular graphs[M]. Theoretical Computer Science, Elsevier Science Publishers Ltd. 2016,609(P2):413-420.
[18] Lai Paolien, Tan Jimmy J M, Chang Chienping, et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005, 54(2):165-175.
[19] Peng Shaolun, Lin Chengkuan, Tan Jimmy J M, et al. The g-good-neighbor conditional diagnosability of hypercube under PMC model[J]. Applied Mathematics and Computation,2012, 218(21):10406-10412.
[20] Yang Weihua, Lin Huiqiu, Qin Chengfu. On the t/k-diagnosability of BC networks[J]. Applied Mathematics and Computation, 2013, 225(12):366-371.
[21] Yuan Jun, Liu Aixia, Ma Xue, et al. The g-good-neighbor conditional diagnosability of kAry n-Cubes under the PMC model and MM*model[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 26(4):1165-1177.
[22] Zhu Qiang, Guo Guodong, Tang Wenliang, et al. A diagnosis algorithm by using graphcoloring under the PMC model[J]. Journal of Combinatorial Optimization, 2016, 32(3):960-969.
[23] Zhang Shurong, Yang Weihua. The g-extra conditional diagnosability and sequential t/kdiagnosability of hypercubes[J]. International Journal of Computer Mathematics, Taylor and Francis, 2016, 93(3):16.
[24] Wu Jie, Huang Ke. The balanced hypercube:a cube-based system for fault-tolerant applications[J]. IEEE Transactions on Computers, 1997, 46(4):484-490.
[25] Yang Mingchien. Bipanconnectivity of balanced hypercubes[J]. Computers and Mathematics with Applications, 2010, 60(7):1859-1867.
[26] Yang Mingchien. Super connectivity of balanced hypercubes[J]. Applied Mathematics and Computation, 2012, 219(3):970-975.
[27] Yang Mingchien, Yang Minghour. Reliability analysis of balanced hypercubes[A]. Computing, Communications and Applications Conference[C]. IEEE, 2012, 376-379.
[28] Lii Huazhong. On extra connectivity and extra edge-connectivity of balanced hypercubes[J].International Journal of Computer Mathematics, 2017, 94(4):8.
[29] Dahbura Anton T, Masson Gerald M. An O(n~(2.5))fault identification algorithm for diagnosable systems[J]. IEEE Computer Society, 1984, 100(6):486-492.
[30] Zhou Jinxin, Wu Zhenlin, Yang Shichen, et al. Symmetric property and reliability of balanced hypercube[J]. IEEE Transactions on Computers, 2015, 64(3):876-881.