版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Peoples R China Jiangxi Univ Sci & Technol Fac Sci Ganzhou 341000 Peoples R China
出 版 物:《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)
年 卷 期:2022年第922卷
页 面:46-60页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:Science and Technology Project of Xinjiang Uygur Autonomous Region [2020D01C069] National Natural Science Foundation of China [12101528, 12001250] Doctoral Startup Foundation of Xinjiang University Xinjiang Key Laboratory of Applied Mathematics [XJDX1401] Tianchi Ph.D Program [tebs201905]
主 题:h-extra edge-connectivity Concentration phenomenon Reliability and fault tolerance Parallel and distributed system Cartesian product lambda(h)-optimality
摘 要:As a measurement parameter of the reliability about interconnection networks of parallel and distributed systems, the h-extra edge-connectivity lambda(h)(G) is a better alternative compared with the classical Menger s theorem of the edge-connectivity. Recently, Li and Yang (2013) [7] determined the values of the h- extra edge-connectivity of hypercube Q(n) for each h = 2(left perpendicularn/2right perpendicular). Because of easy scalability, the interconnection networks based on cartesianproduct operation are extensively investigated. This paper focuses on the h-extra edge-connectivity of the n-th cartesian product of complete graph K-4 with exponentially many faulty links. For a sufficiently large positive integer n, about 60 percent of positive integers hin the interval 1 = h = 2 . 4(n-1) corresponding h-extra edge-connectivity of K-4(n), lambda(h)(K-4(n)), presents a concentration phenomenon, that is, these exact values of lambda(h)(K-4(n)) concentrate on 3 . 4(n-1) and 4(n) for each inverted right perpendicular3 . 4n(-1)/5inverted left perpendicular = h = 4(n-1) and inverted right perpendicular6 . 4(n-1)/5inverted left perpendicular = h = 2 . 4(n-1), respectively. And the lower and upper bounds of hare sharp. Furthermore, the values of lambda(h)(K-2(n)) also have this phenomenon. We obtain lambda(h)(K-4(n)) = 3/2 lambda(h)(K-n2(2)) = 3 . 4(n-1) or lambda(h)( K-4(n)) = 2 lambda(h)(K-n2(2)) = 4(n) in the subintervals where the concentration phenomenon occurs simultaneously. (C) 2022 Elsevier B.V. All rights reserved.