Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks
Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks
复制标题
旋转图：点对点多处理器网络的高效拓扑
DOI：
10.1109/71.159045
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
P. Corbett
中科院分区：
文献类型：
--
作者：
P. Corbett
旋转图，一组有向置换图，被提出作为替代星星和煎饼图。旋转图的定义方式类似于最近提出的Faber-Moore图。它们的直径比星星图或饼图或k元n-立方体的直径小，在一个有n个阶乘顶点的图中直径为n-1。提出了一种简单的旋转图最优路由算法。n-旋转图被定义为所有旋转图的子集。给出了n-旋转图中顶点距离的分布，并求出了顶点之间的平均距离，证明了n-旋转图具有最优容错性和最大一步故障可诊断性。证明了n-旋转图是哈密尔顿图，并给出了在n-旋转图中寻找哈密尔顿回路的算法。>
Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given. >