论文部分内容阅读
研究了一类重要的互连网络拓扑结构Kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合,最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题,在电路测试、操作系统解决死锁、波长转换器安装等领域都有重要的应用.确定一般网络的最小反馈点集问题属于NP问题.由于Kautz图在结点规模、路径长度和容错性上的良好性质,因此适合作为构建高效、容错、可扩展的数据中心网络的拓扑结构,被认为是对超立方体网络的挑战而替代成为下一代的并行计算机互连网络之一.本文通过构造一种算法改进了n≥8时Kautz网络反馈数的渐进公式,同时确定了n=9时Kautz网络的反馈数为精确值.
We study the feedbacks of a class of important interconnected network topological Kautz networks K (d, n). The feedback set of a graph is the set of vertices that need to be removed without G, and the order of minimum feedback set Called the feedback number of G. The feedback set problem is a classical combinatorial optimization problem, which has important applications in the field of circuit testing, operating system to solve deadlock, wavelength converter installation, etc. The problem of determining the minimum feedback point set of a general network belongs to NP problem. Due to the good nature of the Kautz graph in terms of node size, path length and fault tolerance, it is suitable as a topology for constructing an efficient, fault-tolerant, scalable data center network that is considered as a replacement for the challenge of hypercube networks Become one of the next generation parallel computer interconnection networks.In this paper, an asymptotic formula for the feedback number of Kautz network with n ≥ 8 is improved by constructing an algorithm, and the exact number of feedbacks of Kautz network is determined when n = 9.