OTIS网络的支配集问题算法研究

摘要：

图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用,计算上它们都属于NP难问题.OTIS网络是一类可以任意图为因子网络的复合网络,它能继承因子网络的良好特性,因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一.研究如何构建OTIS网络的较小支配集和连通支配集.基于OTIS网络构图规则,分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法.从理论上分析了这些算法的性能,并通过实例进行了验证.

关键词：网络、OTIS网络、图、支配集、连通支配集、算法

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

资助基金：广东省自然科学基金10451063101006313;国家自然科学基金60973150,11071089

在线出版日期：2012-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：93-97