徐喜荣,曹楠,吉日木图,董学智,王保才,王磊.关于折叠超立方体的反馈数[J].,2011,(5):761-765 |
关于折叠超立方体的反馈数 |
On feedback number of folded hypercube |
|
DOI:10.7511/dllgxb201105023 |
中文关键词: 折叠超立方体 无圈子图 超立方体 最小反馈点集 反馈数 |
英文关键词: folded hypercube acyclic subgraph hypercube minimum feedback vertex set feedback number |
基金项目:国家自然科学基金资助项目(10671191;61170303;60973014);高等学校博士学科点专项科研基金资助项目(200801411073);大连理工大学基本科研业务费专项资金资助项目. |
|
摘要点击次数: 1313 |
全文下载次数: 977 |
中文摘要: |
研究了一类重要的互连网络拓扑结构折叠超立方体网络 Q \%f\%n 的反馈数.设F为Q \%f\%n 的反馈集,通过构造剩余子图G V(Q \%f\%n )-F 的极大无圈子图得到极小反馈集,从而得到反馈数的上界,用此方法研究折叠超立方体网络Q \%f\%n 的反馈数问题.根据n维折叠超立方体网络的性质,提出一种新的方法构造无圈子图,改进了已有的n维折叠超立方体网络的反馈数的上界.结果表明,当n为奇数时构造的Q \%f\%n+2 的无圈导出子图的整体连通性能与已有结论中构造的Q n中无圈导出子图R∪Q \%fo\%n 是一致的. |
英文摘要: |
The feedback number of folded hypercube Q \%f\%n , which is an important interconnection network topological structure, is researched. Defining F as a feedback vertex set of Q \%f\%n , maximal acyclic subgraph of survived subgraph G V(Q \%f\%n )-F is construted and a minimal feedback vertex set is achieved. By this approach, the upper bound of feedback number of Q \%f\%n is obtained. According to the property of n- dimensional folded hypercube, a new approach to constructing acyclic subgraph is presented and the upper bound of feedback number of Q \%f\%n is improved. The conclusion indicates that the connectivity of acyclic subgraph of Q \%f\%n+2 constructed by the approach is consistent with the one of acyclic subgraph induced by R∪Q \%fo\%n provided by related results when \%n\% is odd. |
查看全文
查看/发表评论 下载PDF阅读器 |
关闭 |
|
|
|