A new family of Cayley graph interconnection networks of constantdegree four

We propose a new family of interconnection networks that are Cayley graphs with constant node degree 4. These graphs are regular, have logarithmic diameter, and are maximally fault tolerant. We investigate different algebraic properties of these networks (including fault tolerance) and propose optimal routing algorithms. As far as we know, this is the first family of Cayley graphs of constant degree 4     

Comments on “A new family of Cayley graph interconnectionnetworks of constant degree four”

For original paper see Vadapalli and Srimani, ibid., vol. 7, no. 1, p 26-32, 1996, where the authors have proposed a new family of Cayley graph interconnection networks of constant degree four. Our comments show that their proposed graph is not new but is the same as the wrap-around butterfly graph. The structural kinship of the proposed graph with the de Bruijn graph is also discussed     

若干多级互连网络的扩展Cayley图模型

使用群论中的半直积作为工具,将已有的若干构建互连网络的方法统一成一种Cayley图模型CSC（q,p,l,k）,使其具有更好的可扩展性。并证明了CSC（q,p,l,k）网络包括了若干重要的互连网络作为它的特殊情形,例如立方连通圈、星连通圈和最近提出并受到关注的k度Cayley图。提出该模型的意义在于为计算机系统的设计者们提供只需要选择合适的参数就可以确定自己需要的互连网络模型。其次,该模型也在一定程度上避免一些在互连网络构建方面的冗余研究工作。     

One-to-Many Embeddings of Hypercubes into Cayley Graphs Generated by Reversals

Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the degree of regularity are examples such as the ``star' network and the ``pancake' network, the latter a representative of a variety of Cayley graphs generated by reversals. These diameter and degree conditions make these graphs potential candidates for parallel computation networks. Thus it is natural to investigate how well they can simulate other standard parallel networks, in particular hypercubes. For this purpose, constructions have previously been given for low dilation embeddings of hypercubes into star networks. Developing this theme further, in this paper we construct especially low dilation maps (e.g., with dilation 1, 2, 3, or 4) of hypercubes into pancake networks and related Cayley graphs generated by reversals. Whereas obtaining such results by the use of ``traditional' graph embeddings (i.e., one-to-one or many-to-one embeddings) is sometimes difficult or impossible, we achieve many of these results by using a nontraditional simulation technique known as a ``one-to-many' graph embedding. That is, in such embeddings we allow each vertex in the guest (i.e., domain) graph to be associated with some nonempty subset of the vertex set of the host (i.e., range) graph, these subsets satisfying certain distance and connection requirements which make the simulation possible. Received July 30, 1997, and in revised form July 18, 2001. Online publication October 30, 2001.     

计算循环群上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)]。     

关于互连网络的几个猜想

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

Isomorphism of degree four Cayley graph and wrapped butterfly andtheir optimal permutation routing algorithm

In this paper, we first show that the degree four Cayley graph proposed in a paper appearing in the January 1996 issue of IEEE Transactions on Parallel and Distributed Systems is indeed isomorphic to the wrapped butterfly. The isomorphism was first reported by Muga and Wei in the proceedings of PDPTA '96. The isomorphism is shown by using an edge-preserving bijective mapping. Due to the isomorphism, algorithms for the degree four Cayley graph can be easily developed in terms of wrapped butterfly and topological properties of one network can be easily derived in terms of the other. Next, we present the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in time O(√N), where N is the network size     

结构化P2P覆盖网络的Cayley图构造方法研究

结构化P2P覆盖网络通常都基于某个静态的图结构,而这些静态图又常常是Cayley图或其超图,这些静态图的直径、度等特性可以直接影响到覆盖网络拓扑的路由表大小、路由长度等特性,因此静态图的选择显得非常重要.Cayley图是使用代数群论建立的一类图,它的最大好处是其对称性和点传递性,利用Cayley图的这类性质,可以分析结构化P2P覆盖网络拓扑结构的本质.就几种典型的结构化P2P覆盖网络的静态拓扑,分析了其Cayley图构造方法的本质.     

Macro-star networks: efficient low-degree alternatives to stargraphs

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node degree that is considerably smaller than that of a star graph of the same size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree). We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown. This enables us to obtain through emulation a variety of efficient algorithms for the macro-star network, thus proving its versatility. Basic communication tasks, such as the multimode broadcast and the total exchange, can be executed in macro-star networks in asymptotically optimal time under both the single-port and the all-port communication models. Moreover, no interconnection network with similar node degree can perform these communication tasks in time that is better by more than a constant factor than that required in a macro-star network. We show that macro-star networks can embed trees, meshes, hypercubes, as well as star, bubble-sort, and complete transposition graphs with constant dilation. We introduce several variants of the macro-star network that provide more flexibility in scaling up the number of nodes. We also discuss implementation issues and compare the new topology with the star graph and other popular topologies     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

The Cayley network of expanded Pancake graphs

Signed permutation group has important applications in genome rearrangement as well as the construction of networks. In this paper, we propose a new interconnection network named extended Pancake graph, we investigate its topological properties, and give a routing algorithm with the diameter upper bounded by 2n?1. Some embedding properties are also derived. In conclusion, we present a comparison of some familiar networks with the Cayley graph EP _n .     

From the Dandelion Code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality

There are many ways to represent spanning trees in genetic algorithms (GAs). Among them are Cayley codes, which represent each tree on n vertices as a string of (n-2) integers from the set [1,n]. In 2003, Thompson showed that the Dandelion Code, a Cayley code with high locality, offers consistently better performance in a GA than all other known Cayley codes, including the Pru/spl uml/fer Code and the Blob Code. In this paper, we study the Dandelion Code and its properties. We give linear-time implementations of the decoding and encoding algorithms, and prove that the representation has bounded locality and asymptotically optimal locality, unlike all other known Cayley codes. We then modify the Dandelion Code to create bijective spanning tree representations for graph topologies other than the complete graph. Two variations are described: the bipartite Dandelion Code (for encoding the spanning trees of a complete bipartite graph) and the Rainbow Code (for encoding the spanning trees of a complete layered graph). Both variations inherit the Dandelion Code's desirable properties, and have the potential to outperform existing GA representations for computationally hard transportation problems (including the Fixed Charge Transportation Problem) and multistage transportation problems, particularly on large instances.     

Cyclic-cubes: a new family of interconnection networks of evenfixed-degrees

We introduce a new family of interconnection networks that are Cayley graphs with fixed degrees of any even number greater than or equal to four. We call the proposed graphs cyclic-cubes because contracting some cycles in such a graph results in a generalized hypercube. These Cayley graphs have optimal fault tolerance and logarithmic diameters. For comparable number of nodes, a cyclic-cube can have a diameter smaller than previously known fixed-degree networks. The proposed graphs can adopt an optimum routing algorithm known for one of its subfamilies of Cayley graphs. We also show that a graph in the new family has a Hamiltonian cycle and, hence, there is an embedding of a ring. Embedding of meshes and hypercubes are also discussed     

Small-World Networks with Unitary Cayley Graphs for Various Energy Generation

Complex networks have been a prominent topic of research for several years, spanning a wide range of fields from mathematics to computer science and also to social and biological sciences. The eigenvalues of the Seidel matrix, Seidel Signless Laplacian matrix, Seidel energy, Seidel Signless Laplacian energy, Maximum and Minimum energy, Degree Sum energy and Distance Degree energy of the Unitary Cayley graphs [UCG] have been calculated. Low-power devices must be able to transfer data across long distances with low delay and reliability. To overcome this drawback a small-world network depending on the unitary Cayley graph is proposed to decrease the delay and increase the reliability and is also used to create and analyze network communication. Small-world networks based on the Cayley graph have a basic construction and are highly adaptable. The simulation result shows that the small-world network based on unitary Cayley graphs has a shorter delay and is more reliable. Furthermore, the maximum delay is lowered by 40%.     

Cayley graphs as models of deterministic small-world networks

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.     

具有高对称性的小世界网络模型研究

在研究小世界网络和Cayley图的基础上,采用基于Cayley图的代数图论方法,给出一种具有高对称性的小世界网络模型,分析该模型的聚类系数和特征路径长度等小世界性质,给出其路由算法。分析结果表明,该模型聚类性高、网络直径小,具有小世界特性。     

Geometric spanners for wireless ad hoc networks

We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.     

Cube connected Mobius ladders: an inherently deadlock-free fixeddegree network

The authors introduce a multiprocessor interconnection network, known as cube-connected Mobius ladders, which has an inherently deadlock-free routing strategy and hence has none of the buffering and computational overhead required by deadlock-avoidance message passing algorithms. The basic network has a diameter φ of 4n-1 for n2ⁿ⁺² nodes and has a fixed node degree of 4. The network can be interval routed in two stages and can be represented as a Cayley graph. This is the only practical fixed degree topology of size O(2^φ) which has an inherently deadlock-free routing strategy, making it ideally suited for medium and large sized transputer networks     

Reversals Cayley graphs of symmetric groups

Corresponding to genome rearrangements by reversals, we propose a new reversal Cayley graph RSn as the Cayley graph Cay(Sn,Ωn), where Sn is the symmetric group of degree n and Ωn is the set of all reversals of Sn. Graph properties including connectivity, diameter and hamiltonicity, are investigated for this kind of graphs.     

Optimal information dissemination in star and pancake networks

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps