Mbius立方体互连网络上的圈嵌入算法

• 全文链接
• 请求原文

作   者：

樊建席;  逯昭义; 

作者机构：

青岛大学计算机与信息科学系; 

关键词：

嵌入，扩张，圈，Mbius立方体，互连网络; 

期刊名称：

计算机研究与发展

i s s n：

1000-1239

年卷期：

1998 年 11 期

页   码：

摘   要：

图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术．文中讨论了近年提出的一类互连网络——Ｍｏｂｉｕｓ立方体上的圈嵌入性质．Ｍｏｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立方体更优越的性质，如ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ的直径大约是ｎ维超立方体的一半，其期望距离大约是ｎ维超立方体的２３等．文中证明了Ｍｏｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２ｎ）的圈能以扩张ｌ嵌入ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ（ｎ≥２），并给出了构造过程，从而也证明Ｍｎ对环网络的模拟能力比超立方体的高（超立方体不含奇长圈）．...