摘要
给出了一类图 (迪卡尔乘积图 )到另一类图 (Cayley图 )的嵌入的一般方法 .这些嵌入是这样实现的 :首先把迪卡尔乘积图的每个“因子”图嵌入到主图中 ,然后取这些“因子”嵌入的积 .进一步给出了一个定理 ,用来通过“因子”嵌入的性质来计算乘积嵌入的膨胀度 .
Finding a good topology for multiprocessor interconnected network is a problem that is widely discussed recently, and many topologies have been recommended, such as hypercube, generalized hypercube and the recently proposed class of graphs——Cayley Graphs, among which is star graph, which is looked on as an attractive alternative to hypercube. One problem in dealing with the newly proposed topology is the lack of algorithms tailored for them, which impede the application of these network topologies. In order to solve this problem, embeddings of graphs are considered. With the embedding of one graph into another, the host can employ algorithms proposed for the vip. However, in the previous efforts, only the embeddings of some particular graphs were discussed. In this paper, the general method of embedding a kind of graphs, Cartesian product graphs, into another kind of graphs, Cayley graphs, is presented. These embeddings are carried out by first embed the factor graphs of the Cartesian product graphs into the hosts, then take the products, which is a concept introduced in this paper, of these factor embeddings. A theorem is given which presents a method to compute the dilation of the product embedding from the properties of the “factor embeddings”.
出处
《计算机学报》
EI
CSCD
北大核心
2000年第6期646-648,共3页
Chinese Journal of Computers
关键词
CAYLEY
迪卡尔乘积图
互联网
体系结构
embedding of graphs,Cayley graph,Cartesian product graph,product of embeddings
