Hits:

Indexed by:期刊论文

Date of Publication:2014-03-19

Journal:大连理工大学学报

Included Journals:PKU、ISTIC、CSCD

Volume:54

Issue:2

Page Number:262-266

ISSN No.: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().