Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2014-03-19

Journal: 大连理工大学学报

Included Journals: CSCD、ISTIC、PKU

Volume: 54

Issue: 2

Page Number: 262-266

ISSN: 1000-8608

Key Words: 局部扭立方体 独立集 无圈子图 反馈数 locally twisted cube independent set acyclic subgraph feedback number

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