| HCH-立方体的Hamilton连通性 |
| |
| 引用本文： | 刘昕,樊建席,宗绪锋,徐翠霞. HCH-立方体的Hamilton连通性[J]. 计算机工程与应用, 2005, 41(32): 83-86 |
| |
| 作者姓名： | 刘昕 樊建席 宗绪锋 徐翠霞 |
| |
| 作者单位： | 潍坊学院计算机科学系,山东,潍坊,261043;青岛大学信息工程学院,青岛,266071 |
| |
| 摘 要： | 新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。
|
| 关 键 词： | 互连网络 HCH-立方体 超立方体 交叉立方体 Hamilton-路 Hamilton连通性 |
| 文章编号： | 1002-8331-（2005）32-0083-04 |
| 收稿时间： | 2005-02-01 |
| 修稿时间： | 2005-02-01 |
Hamilton-connectivity on HCH-cubes |
| |
| Liu Xin,Fan Jianxi,Zong Xufeng,Xu Cuixia. Hamilton-connectivity on HCH-cubes[J]. Computer Engineering and Applications, 2005, 41(32): 83-86 |
| |
| Authors: | Liu Xin Fan Jianxi Zong Xufeng Xu Cuixia |
| |
| Abstract: | The research and production of new parallel computing systems depend on the research of new interconnection network structures and their properties.The hypercube and the crossed cube,as a variant of the hypercube,have both merits and defects.[1] gives a kind of connection- the hyper connection between the nodes of the hypercube and the crossed cube.Thus a interconnection network called a HCH- cube is obtained.This paper proves that HCH- cube is Hamilton- connected.The relative algorithm of the process of finding Hamilton paths is also given.The time complexity of this algorithm is O(N),N=2n. |
| |
| Keywords: | interconnection network HCH-cube hypercube crossed cube Hamilton path Hamilton-connectivity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
