互连网络拓扑结构图的反馈数、算法及应用研究

项目名称： 互连网络拓扑结构图的反馈数、算法及应用研究

项目编号： No.61170303

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 自动化技术、计算机技术

项目作者： 徐喜荣

作者单位： 大连理工大学

项目金额： 52万元

中文摘要： 本项目是研究互连网络拓扑结构图的反馈数问题，它是计算机科学与组合数学和图论交叉的研究课题。图的反馈数问题来源于实际问题，在诸多领域如预防计算机死锁，互连网避免广播风暴以及电子电路检测等问题中有着广泛的应用。已经被证明求图的反馈数问题是NP困难问题，研究它对解决一般NP困难问题有借鉴意义。 本项目旨在研制出较好的计算图的反馈数的算法，并以此研究与互连网络拓扑结构相关图的反馈数；确定与互连网络拓扑结构相关图的反馈数的紧的上下界；同时研究一般图的反馈数尽可能紧的上下界；从而能更好的解决与反馈数有关的实际问题。 本项目的研究将丰富利用计算机算法解决图论问题的理论成果，对互连网络拓扑结构相关图的反馈数的研究结果对互连网络的设计、网络性能的定量分析和评估起着重要的理论指导作用，也为下一代超大规模超级计算机系统的互连网络的设计提供进一步的理论依据。

中文关键词： 反馈数；最小反馈点集；最小反馈边集；网络拓扑结构；算法

英文摘要：

英文关键词： feedback number；minimum feedback vertex set；minimum feedback edge set；network topological structure；algorithm