作者：陈卫东互连网络支配集连通支配集np难度近似算法
摘要：图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名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网络等组合网络中的大数据处理和分析提供了一条可行途径.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
