完全二叉树到冒泡排序网络的嵌入

Embedding Complete Binary Trees into Bubble Sort Networks

冒泡排序网络是由凯莱图模型设计出来的重要的互连网络.这个网络由于它的简单,点对称性和可缩结构而受到极大关注.二叉树是并行通信模式中应用十分普遍的结构.设G和H是两个给定的网络,它们可分别由两简单无向图表示,从G到H的嵌入是存在G到H的同态映射使得对G中的任何一条边,它的象是H中一条路.把二叉树嵌入到另一网络中,这样可以应用已知的二叉树的性质去研究另一网络,反过来可以用另一网络模拟二叉树.在本文中我们主要考虑完全二叉树,同根完全二叉树和双根完全二叉树能以膨胀数1嵌入到冒泡排序网络中,同时给出了这三种完全二叉树嵌入冒泡排序网络的具体构造方法.

Bubble sort netwoks are important interconnection networks designed from the Cayley graph model. Bubble-sort networks are attracting more and more attention because of their simple, symmetric, and recursive structure. Binary trees are a common structure to represent the communi- cation pattern of a parallel algorithm. Let G and H be two networks represented by simple undirected graphs, an embedding of G into H is an injective mapping ~ from the edge set of G into the path set of H. Embedding binary trees into another network--the host network--helps in finding solutions for the host network by using the known solutions on binary trees, while the host network can also stimulate the binary tree. In this paper, we consider the problem how to embed a complete binary tree, the same-rooted complete binary tree and the double-rooted complete binary tree into the n-dimensional bubble sort networks with dilation 1. In addition, we give the concrete construction of embedding of these complete binary trees into bubble sort networks with dilation 1.