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

Estimations for Diameters of Undirected Double Loop Networks

设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.