一种求解Kautz图K(d,n)反馈数的改进算法

摘要 研究了一类重要的互连网络拓扑结构Kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合，最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题，在电路测试、操作系统解决死锁、波长转换器安装等领域都有重要的应用.确定一般网络的最小反馈点集问题属于NP问题.由于Kautz 图在结点规模、路径长度和容错性上的良好性质，因此适合作为构建高效、容错、可扩展的数据中心网络的拓扑结构，被认为是对超立方体网络的挑战而替代成为下一代的并行计算机互连网络之一.本文通过构造一种算法改进了n≥8时Kautz网络反馈数的渐进公式，同时确定了n=9时Kautz网络的反馈数为精确值