Bi-swapped网络的支配集问题研究

• 作者: 陈卫东
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 互连网络 Bi-swapped网络 支配集 连通支配集 NP难度 近似算法
• 年，卷（期）: 2016,（12）
• 所属期刊栏目: 量子计算、计算机理论与算法
• 页码范围: 2512-2526
• 页数: 15页
• 分类号: TP301
• 字数: 16437字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.02512

摘要

图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起来.Bi-swapped网络的优良特性使得它可为构建并行计算机提供潜在有竞争力的体系结构方案.文中基于Bi-swapped网络的互连规则研究Bi-swapped网络中最小支配集问题和最小连通支配集问题.首先证明这两个问题都是NP难度的,然后基于Bi-swapped网络的模块化结构特性,给出求解这两个问题的几个简单有效的近似算法.在一个N节点的Bi-swapped网络中,文中的算法以因子网络的一个(连通)支配集为输入,在O(N)时间内能构造出Bi-swapped网络的一个(连通)支配集,并且以一定性能保证了所构造的(连通)支配集的质量.相比之下,如果将Bi-swapped网络视作一般图而不利用其模块化特性,直接构造一个同样质量的(连通)支配集则需要O(N2)时间.该文也建立了因子网络和Bi-swapped网络的(连通)支配数之间的联系,由此获得Bi-swapped网络的(连通)支配数的非平凡的上下界.我们的方法为诸如Bi-swapped网络等组合网络中的大数据处理和分析提供了一条可行途径.

作者信息

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