摘要
研究了一类重要的互连网络拓扑结构Kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合,最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题,在电路测试、操作系统解决死锁、波长转换器安装等领域都有重要的应用.确定一般网络的最小反馈点集问题属于NP问题.由于Kautz图在结点规模、路径长度和容错性上的良好性质,因此适合作为构建高效、容错、可扩展的数据中心网络的拓扑结构,被认为是对超立方体网络的挑战而替代成为下一代的并行计算机互连网络之一.本文通过构造一种算法改进了n≥8时Kautz网络反馈数的渐进公式,同时确定了n=9时Kautz网络的反馈数为精确值.
The feedback number of Kantz digraphs K （ d, n）, which is an important interconnection network topological structure, is re- searched in this paper. The feedback vertex set of a graph is a vertex subset which results in an acyclic graph when it is removed. The minimum cardinality of a feedback vertex set is called feedback number. The feedback set problem is originally formulated in the area of combinatorial circuit design. It has important applications in circuit testing, deadlock resolution and the wavelength converter instal- lation, et al. The minimum feedback set problem is known to be NP-hard for general graphs. Because of Kautz graphs excellent proper- ties in node degree, path length and fault tolerance to build efficient, fault-tolerant and scalable DCN, it has been thought of as a good candidate for the next generation of parallel system architectures, after the hypercube network. In this paper, we present an algorithm for constructing a feedback vertex set of K （ d, n ） . We improve the upper bound of feedback number of K （ d, n ） for n ≥ 8 and deter- mined the exact values for n = 9.
出处
《小型微型计算机系统》
CSCD
北大核心
2016年第10期2279-2284,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61170303
61472465
61562066)资助
关键词
Kautz图
反馈集
无圈子图
消圈数
反馈数
Kautz graph
feedback vertex set
acyclic subgraph
decycling number
feedback number
