小世界网络的Cayley图模型

Internet网络中小世界特征的发现激起了学术界对Internet小世界网络的研究热潮。提出了一种基于Cayley图的小世界网络模型（CSWN）,该模型具有高聚集性和小网络直径;在分析了该网络模型的一些主要性质后给出了其路由算法;最后通过仿真实验证明了该模型符合小世界网络的特性。     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

多级互连网络的图分析与设计法

本文介绍一种多级互连网络的图分析与设计方法。这种方法对分析网络间的拓扑等价关系,比较网络间的置换特性和计算网络实现无冲突置换所需的通过次数都十分简便,同时对满足给定置换函数要求,设计出合理的网络拓扑也十分有效。     

多级互连网络互连函数的矩阵理论

多级互连网网络是大规模并行处理系统和大型ＡＴＭ交换机采用的主要互连结构。     

扩充混洗交换多级互连网络

扩充混洗交換多导互连网络主要解决各级开关的单容错性,不同溯重选择路径能力,联机修复故障元件能力,开关复杂性和链接复杂性。在许多特性方面。它比原来的多级互联网络要好得多。     

互连网络的m层二进制图模型

超立方体、交叉立方体、Mbius立方体以及折叠立方体等都是著名的互连网络。它们有一个共同的弱点:其结点度随着网络规模(结点数)的增大而增大。这意味着依此互连网络设计出的超级计算机的扩展性很差。能否构建出既能保持它们已有特性又能使结点度固定的互连网络呢？现提出互连网络的m层二进制图模型,并依此模型设计了分别由超立方体、交叉立方体、Mbius立方体以及折叠立方体等生成的m层超立方体、m层交叉立方体、m层Mbius立方体以及m层折叠立方体。特别地,m层超立方体有一个特点:结点度可以不随网络规模的增大而增大,而且具有超立方体的特性。另外,还提出了由已知图生成m层图的概念。     

多级互连网络有效带宽研究

1.基本假定 大型多处理机系统的处理机——存贮器互连网络往往采用多级网络.文献[1]讨论了当处理机访存请求为均匀分布时,Delta网络的有效存贮器带宽。文献[2]在此基础上分析了当存在偏爱存贮体时的有效带宽。设处理机数为P,存贮体数为M,文献[2]的分析基于如下假定:     

多级互连网络中的multicast通信

ＭＰＰ系统中的并行通信是目前并行处理研究的热点，改善并行通信性能，提高网络吞吐率是促进ＭＰＰ性能发挥的关键问题。ｍｕｌｔｉｃａｓｔ通信是区别于点到点通信的一对多通信方式，因而功能更强大，使用起来更灵活方便，在并行处理中应用十分广泛。文中以基于开关元件实现结点间动态互连的多级互连网络为背景，研究了ｍｕｌｔｉｃａｓｔ通信路上算法的效率。     

基于Cayley图的六度环绕网络研究

六度网络是一类平面图网络结构,将平面以等边三角形的形式进行分割,包括六度网孔网络和六度环绕网络.六度网孔网络不是规则网络,其边缘节点与内部节点的度不相等.通过对六度网孔网络的边缘节点建立环绕边就形成了规则的六度环绕网络,每个节点的度为6.但是由于环绕边的存在,使得六度环绕网络的通信算法实现复杂,网络直径也非常难于计算.六度环绕网络被证实是一种Cayley图模型,具有良好的对称性.但是基于Cayley图的六度环绕网络的最优路由算法、广播算法还没有得到,该网络模型的具体直径值也是未解问题.针对基于Cayley图的六度环绕网络模型,文中给出了一种简单的最优路由算法和一种基于陪集图理论的广播算法,并给出该网络模型的网络直径确切值.     

基于Cayley图的Cycloid网络中主节点备份模型设计

介绍了P2P网络的发展现状和结构化P2P网络的特性,根据P2P网络的优点分析了其中一种较新近的结构化P2P网络--Cycloid网络的Cayley图原型及其主节点的连接情况,并基于对主节点失败情况所出现的不理想等待状况的分析,提出了备份设计模型,并采用类的对象的方法来模拟网络中的节点,进行了编程模拟实验,证实了该模型设计具有现实可行性和节约时问的特性.     

迪卡尔乘积图到Cayley图中的嵌入

给出了一类图（迪卡尔乘积图）到另一类图（Ｃａｙｌｅｙ图的嵌入的一般方法,这些嵌入是这样实现的：首先把迪卡尔乘积图的每个“因子”图嵌入到主图中,然后取这些“因子”嵌入的积,进上步给出了一个定理,用来通过“因子”嵌入的性质来计算乘积嵌入的膨胀度。     

Honeycomb toroidal graphs are Cayley graphs

There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups.     

The pessimistic diagnosability of alternating group graphs under the PMC model

The process of identifying faulty processors is called the diagnosis of the system. Several diagnostic models have been proposed, the most popular is the PMC (Preparata, Metze and Chen) diagnostic model. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty nodes within a set containing at most one fault-free node. A system is t/t$t/t$-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G  , denoted by _tp(G)$t_p(G)$, is the maximal number of faulty processors so that the system G   is t/t$t/t$-diagnosable. Jwo et al. [11] introduced the alternating group graph as an interconnection network topology for computing systems. The proposed graph has many advantages over hypercubes and star graphs. For example, for all alternating group graphs, every pair of vertices in the graph are connected by a Hamiltonian path and the graph can embed cycles with arbitrary length with dilation 1. In this article, we completely determine the pessimistic diagnosability of an n  -dimensional alternating group graph, denoted by _AGn${\mathit{AG}}_n$. Furthermore, _tp(_AGn)=4n−11$t_p({\mathit{AG}}_n)=4n-11$ for n≥4$n\ge 4$.     

Linearly many faults in Cayley graphs generated by transposition trees

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.     

One conjecture of bubble-sort graphs

The bubble-sort graph is an important interconnection network designed from Cayley graph model. One conjecture is proposed in Shi and Lu (2008) [10] as follows: for any integer n?2, if n is odd then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles and its perfect matching that has no edges in common with the hamiltonian cycles. In this paper, we prove that conjecture is true for n=5,6.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

计算循环群上4度Bi-Cayley网络直径的快速算法

Cayley图是一类高对称正则图,有许多好性质,被广泛认为是一类理想的互连网络拓扑结构。Bi-Cayley图是Cayley图的一个自然推广,特别地,循环群上4度Bi-Cayley网络[BC(n;±s1,±s2)]是双环网络[DLG(n;±s1,±s2)]的一个自然推广。讨论了循环群[?n]上4度Bi-Cayley网络[BC(n;±s1,±s2)]连通的充分必要条件,并给出了计算该网络直径的一种算法,其时间复杂度为[O(lb n)]。