CAJ | 학술논문

确定一般网络(或图)的最小反馈点集问题属 NP 难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn 的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn .根据Ql tn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-11- cn-1().
학정일반망락(혹도)적최소반궤점집문제속 NP 난문제.n유국부뉴립방체망락Qltn시n유초립방체망락Qn 적변형차시일류중요적호련망락탁복결구,기옹유적모사성질우우Qn .근거Ql tn정점집합중최후일위자절불동적특점,장기정점집합화분위량개불상교적자집,통과구조겁대무권자도득도반궤수적상계,병증명료대임의정정수n≥2,존재상수c∈(0,1)사득반궤수위f(n)=2n-11- cn-1().
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).