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

• 作者: 叶慧 向永香 李旻 陈卫东
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 网络 OTIS网络 图 支配集 连通支配集 算法
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 93-97
• 分类号: TP301
• 字数: 6839字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.03.020

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈卫东	华南师范大学计算机学院	14	71	4.0	8.0
2	叶慧	华南师范大学计算机学院	2	1	1.0	1.0
3	向永香	华南师范大学计算机学院	1	1	1.0	1.0