无向双环网络直径的估计(英文)  

Estimations for Diameters of Undirected Double Loop Networks

作　　者：陈宝兴[1] 肖文俊[2] 黄晓农[3] 

机构地区：[1]漳州师范学院计算机科学系,福建漳州363000 [2]华南理工大学计算机科学系,广东广州510641 [3]漳州师范学院数学系,福建漳州363000

出　　处：《漳州师范学院学报（自然科学版）》2005年第2期7-12,6,共7页Journal of ZhangZhou Teachers College（Natural Science)

基　　金：Supported by the Scientific Research Foundation of Fujian Provincial Education Department(JA04249) the Scientific Research Foundation of Zhangzhou Teacher’s College (L20445)

摘　　要：设h,n是满足条件2≤h<n/2的两个正整数.无向双环网络G(n,1,h)是一个无向图(V,E),这里顶点集VZ{0,1,2,,n-1}n==…,边集E={i→i+1(modn),i→i-1(modn),i→i+h(modn),i→i-h(modn)|i=0,1,2,…,n-1}.双环网络在并行处理的互连网络与局域通信网络的设计中有着重要的应用.利用G(n,1,h)的直径与平行四边形中格点间距离的关系,我们给出了无向双环网络G(n,1,h)新的直径上界估计.设n=qh+r,这里0≤r<h.当q<r时,我们所给出的上界估计比D.Z.Du等人所给的上界估计精确.Let 2 ≤ h<n/2. An undirected double loop network G(n, 1, h) is a graph (V, E), where VZ {0, 1, 2, , n-1} n = =…, and E = {i→i+1(mod n), i→i-1(mod n) , i→i+h(mod n), i → i-h(mod n)| i=0, 1, 2, …, n-1}. Double loop networks are applicable in the design of interconnection networks for parallel processing and of local area communication networks. By using the relationship between the diameter of G(n, 1, h) and distances of lattice points in a parallelogram, some new upper bound estimations for diameters of undirected double loop networks are given. Let n=qh+ r, where 0 ≤ r<h. Our upper bound estimation is more accurate than the estimations given by D. Z. Du and others when q < r.

关 键 词：网络直径 双环网络 上界估计 平行四边形 通信网络 互连网络 并行处理 正整数 无向图 顶点集 边集 距离 格点 

分 类 号：O157.5[理学—数学] TP393.02[理学—基础数学]