点击次数：

论文类型：期刊论文

发表时间：2014-03-19

发表刊物：大连理工大学学报

收录刊物：PKU、ISTIC、CSCD

卷号：54

期号：2

页面范围：262-266

ISSN号：1000-8608

关键字：局部扭立方体 独立集 无圈子图 反馈数 locally twisted cube independent set acyclic subgraph feedback number

摘要：确定一般网络(或图)的最小反馈点集问题属 NP 难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn 的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn .根据Ql tn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-11- cn-1().