On the generalization of the pancake network
On the generalization of the pancake network
复制标题
论煎饼网络的泛化
DOI：
10.1109/ispan.2002.1004278
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
I. H. Sudborough
中科院分区：
文献类型：
--
作者：
M. Justan;F. P. Muga;I. H. Sudborough
在这项研究中，我们对一类对称互连网络特别感兴趣，即煎饼图 P/sub n/。煎饼图对于分布式处理特别有吸引力，因为它们与类似大小的超立方体相比具有优势。它们的度数和直径比相应大的超立方体小。单边煎饼图 P/sub n/ 已建模为 n 阶对称群 S/sub n/ 上的凯莱图，而双边煎饼图 2P/sub n/ 已表示为花环积 S/sub 2//spl bsol/S/sub n/ 上的凯莱图。在本文中，我们想要推广煎饼图，即陈述 m 边煎饼翻转问题，并将其图描述为 m 边煎饼图，mP/sub n/。具体来说， 1. 我们将 m 边煎饼图 mP/sub n/ 建模为一些有限群的花环乘积上的凯莱图；那么，2.我们将研究m边煎饼图的度、直径和路由协议，mP/sub n/； 3. 我们将给出 mP/sub n/ 直径的界限； 4. 对于 1 /spl les/ n /spl les/ 6，我们将给出 3P/sub n/ 的直径。
In this study, we are particularly interested in one class of symmetric interconnection networks, namely the pancake graph, P/sub n/. Pancake graphs are especially attractive for distributed processing because they compare favorably with a hypercube of similar size. They have smaller degree and diameter than correspondingly large hypercubes. The one-sided pancake graph, P/sub n/, has been modeled as a Cayley graph on S/sub n/, the symmetric group of order n, while the two-sided pancake graph, 2P/sub n/, has been represented as a Cayley graph on the wreath product S/sub 2//spl bsol/S/sub n/. In this paper, we want to generalize the pancake graph, i.e., state the m-sided pancake flipping problem, and describe its graph as the m-sided pancake graph, mP/sub n/. Specifically, 1. we shall model the m-sided pancake graph, mP/sub n/ as Cayley graph on the wreath product of some finite groups; then, 2. we shall look into the degree, diameter and the routing protocol of the m-sided pancake graph, mP/sub n/; 3. we shall give the bounds for the diameters of mP/sub n/; and, 4. we shall give the diameters of 3P/sub n/ for 1 /spl les/ n /spl les/ 6.