摘要
研究了超立方体中任意两个不同顶点之间的路径嵌入问题,用构造法证明了结论在超立方体中,如果两个顶点之间的距离为奇数(偶数)并且被嵌入的路径的长度也是奇数(偶数),那么所有可能长度的路径都能以扩张1嵌入到两个顶点之间;如果两个顶点之间的距离是偶数(奇数)但被嵌入的路径的长度是奇数(偶数),那么所有可能奇(偶)长度的路径都不能以扩张1嵌入到两个顶点之间。该研究解决了超立方体中任意两顶点间所有可能长度的非容错路径嵌入问题。
In this paper, we study path embeddings between any two distinct nodes in hypercubes. By using constructive method, we prove the following results in the hypercube: Paths of all possible lengths can be embedded between any two nodes with dilation 1 if the lengths of the paths are odd (even) and the distance between the two nodes is also odd (even) ; Paths of all possible even (odd) lengths cannot be embedded between the two nodes with dilation 1, if the lengths of the paths are odd (even) but the distance between the two nodes is even (odd). This research has solved the problem for fault-free embeddings of paths of all possible lengths in hypercubes.
出处
《青岛大学学报(工程技术版)》
CAS
2006年第3期54-58,共5页
Journal of Qingdao University(Engineering & Technology Edition)
关键词
互连网络
超立方体
图嵌入
最优嵌入
并行计算系统
interconnection network
hypercube
graph embedding
optimal embedding
parallel computing system