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

Algorithms for Dominating Set Problems in OTIS Networks

作　　者：向永香[1] 叶慧[1] 李旻[1,2] 陈卫东[1] 

机构地区：[1]华南师范大学计算机学院,广州510631 [2]华南师范大学招生办,广州510631

出　　处：《计算机科学》2012年第3期93-97,共5页Computer Science

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

摘　　要：图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用,计算上它们都属于NP难问题。OTIS网络是一类可以任意图为因子网络的复合网络,它能继承因子网络的良好特性,因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一。研究如何构建OTIS网络的较小支配集和连通支配集。基于OTIS网络构图规则,分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法。从理论上分析了这些算法的性能,并通过实例进行了验证。The minimum dominating set problem and the minimum connected dominating set problem, both of which are NP-hard problems, have many important applications in the fields rented to networks and parallel ~ distributed computing. Recent OTIS networks are a class of two-level structure interconnection networks taking any graph as modules and connecting them in a complete graph manner, which provides a systematic competitive construction scheme for large, scaNble,moduNr,and robust parallel architectures while maintaining favorable properties of their factor networks. In this paper,how to construct a small dominating set and connected dominating set of an OTIS network was discussed. Based on the connectivity rule of OTIS networks,we gave algorithms for constructing a small dominating set （a small connected dominating set, respectively） of an OTIS network from a dominating set （a connected dominating set, respectively） of its factor network. The performances of these algorithms were analyzed,and were shown by examples.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]