关于局部扭立方体的反馈数

摘要

The minimum feedback point set problem is known to be NP-hard for general network (graphs).As an important interconnection network topological structure,the n-dimensional locally twisted cube network Qltn is a new variant of n-dimensional hypercube network Qn,which possesses some properties superior to those of Qn.Since the last bytes in vertex set of Qltn are different,vertex set of Qltn is divided into two disjoint subsets.By constructing a maximal acyclic subgraph of Qltn,the upper limit of feedback number is attained.It is proved that for any positive integer n≥2,there is a constant c∈(0,1),which makes the feedback number of Qltn as follows:f(n)=2n-1(1-c/n-1).%确定一般网络(或图)的最小反馈点集问题属 NP 难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn 的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn .根据Ql tn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-11- cn-1().