奇异k紧优双环网络无限族的构造

提出构造任意奇异k紧优双环网络无限族的一种方法.对于整数k>12m+3+(2i-1)224,m≥i-i2-13,设N(t)=3t2+(2i-1)t+B,其中B=k2+k-m,1≤i≤3且N(t)∈Ii(t),证明了对于若干组i和m,可以构造奇异k紧优双环网络无限族.

The construction of infinite families of any k-tight optimal and singular k-tight optimal directed double loop networks

The double loop network(DLN)is a circulant digraph with n nodes and outdegree 2.It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems.Given the number n of nodes,how to construct a DLN which has minimum diameter?This problem has attracted great attention.A related and longtime unsolved problem is:for any given non-negative integer k,is there an infinite family of k-tight optimal DLN?In this paper,two main results are obtained:(1)for any k≥0,the infinite families of k-tight optimal DLN can be constructed,where the number n(k,e,c)of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c.(2)for any k≥0, an infinite family of singular k-tight optimal DLN can be constructed.

A new method for constructing infinite families of k-tight optimal double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. DLN has been widely used in the designing of local area networks and distributed systems. In this paper, a new method for constructing infinite families of k-tight optimal DLN is presented. For k = 0,1,…,40, the infinite families of k-tight optimal DLN can be constructed by the new method, where the number nk(t,a) of their nodes is a polynomial of degree 2 in t and contains a parameter a. And a conjecture is proposed.

奇异k-紧整数无限族

设n,s1,s2是3个正整数,使得s1<s2<n,gcd(n,s1,s2)=1.双环网G(n;s1,s2)是个有向图,其结点集为V={0,1,2,L,n?1},其弧集为A={i→i+s1(modn),i→i+s2(modn)|i∈V},s1和s 2称为步长.设d(n;s1,s2)为双环网G(n;s1,s2)的直径.令d(n)=min{d(n;s1,s2)|s1<s2<n},d 1(n)=min{d(n;1,s)|1<s<n}.已知d 1(n)≥d(n)≥?3n??2=lb(n).若d(n;s1,s2)=d(n)=lb(n)+k(k≥0),则称G(n;s1,s2)是个k-紧优的双环网.虽然等式d 1(n)=d(n)对于无限多个整数n成立,但也存在无限多个整数n使得d 1(n)>d(n),这样的n称为奇异整数.若d 1(n)>d(n)=lb(n)+k,k≥0,则这样的n称为奇异k-紧整数.本文给出构造奇异k-紧整数无限族的方法,并对于k=1,2,L,20,构造出这样的无限族.

含参数的k紧优双环网的无限族

本文得到了含参数的3紧优和4紧优双环网的无限族,其结点数形如n(e,m)=U(e)+V(m),这里U(e)和V(m)都是2次多项式,e相对于m充分大.

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.

k-紧优有向双环网络无限族的构建

本文给出了一种方法用于构造k-紧优双环网络无限族(k≥1),并用此方法构造出了4族3-紧优无限族,3族新的4-紧比无限族,3族5-紧优无限族及2族6-紧优无限族．

k紧优双环网的无限族的构造

双环网是计算机互连网络和通讯系统的一类重要拓扑结构,已广泛应用于计算机互连网络拓扑结构的设计中,利用L形瓦理论,结合中国剩余定理和二次同余方程的性质,给出了不同于参考文献中的任意k紧优双环网的无限族的构造方法,证明了对任意正整数k,若n(t)=3t^2+At+B,A=1,3,5,对于一定的B>(k+1)~2,均存在正整数t,使得{G(n(t);s(t))}是k紧优双环网的无限族,而且这样的无限族有无穷多类.作为定理的应用,给出了多类新的k紧优双环网的无限族.