关于莫比乌斯立方体上独立生成树的构造
owards the Construction Problem of ISTs on M?bius Cubes
独立生成树能够用来提高广播方案的容错性和传输协议的安全性。国内外相关研究学者已经在超立方体、局部扭立方体、扭立方体等网络上取得了一些成果，但迄今为止，在莫比乌斯立方体上还没有关于独立生成树的存在性及构造问题的报道。本文证明了在 维莫比乌斯立方体0-Mn 上以顶点0为根存在 棵独立生成树；提出了一个时间复杂度为O(NlogN) 的递归构造算法，这里n≥2 且N=2n 是0-Mn 上的顶点个数。
Multiple independent spanning trees (ISTs) can be used in broadcasting schemes and distribution protocals to provide high levels of fault-tolerance and security, respectively. Some results have been found on Qn,LTQn,TQn, etc, but so far no work has been reported on 0-Mn . In this paper, we study the exitence and construction of ISTs on M?bius cubes. We give a proof of the existence of ISTs rooted at vertex 0 on the n-dimentional M?bius cube 0-Mn and propose an O(NlogN) recursive algorithm, where n≥2 and N=2n is the number of vertices in 0-Mn.
程宝雷、樊建席
计算技术、计算机技术
算法理论莫比乌斯立方体独立生成树顶点不相交容错广播
M?bius cubesIndependent spanning treeInternally vertex-disjoint pathFault-tolerant broadcasting
程宝雷,樊建席.关于莫比乌斯立方体上独立生成树的构造[EB/OL].(2011-04-08)[2025-08-24].http://www.paper.edu.cn/releasepaper/content/201104-205.点此复制
评论