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

Dominating Set Problems in Bi-swapped Networks

作　　者：陈卫东[1] 

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

出　　处：《计算机学报》2016年第12期2512-2526,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(61370003);教育部留学回国人员科研启动基金资助~~

摘　　要：图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起来.Bi-swapped网络的优良特性使得它可为构建并行计算机提供潜在有竞争力的体系结构方案.文中基于Bi-swapped网络的互连规则研究Bi-swapped网络中最小支配集问题和最小连通支配集问题.首先证明这两个问题都是NP难度的,然后基于Bi-swapped网络的模块化结构特性,给出求解这两个问题的几个简单有效的近似算法.在一个N节点的Bi-swapped网络中,文中的算法以因子网络的一个(连通)支配集为输入,在O(N)时间内能构造出Bi-swapped网络的一个(连通)支配集,并且以一定性能保证了所构造的(连通)支配集的质量.相比之下,如果将Bi-swapped网络视作一般图而不利用其模块化特性,直接构造一个同样质量的(连通)支配集则需要O(N^2)时间.该文也建立了因子网络和Bi-swapped网络的(连通)支配数之间的联系,由此获得Bi-swapped网络的(连通)支配数的非平凡的上下界.我们的方法为诸如Bi-swapped网络等组合网络中的大数据处理和分析提供了一条可行途径.The concepts of dominating set （DS） and connected dominating set （CDS） in graph theory are applicable to resource layouts and routing strategies in parallel and distributed systems. Bi-swapped networks （BSNs）, an improved version of well-known swapped networks （SNs）, are a class of combinatorial network architectures that take multiple copies of any factor network as modules and connect these modules in a simple swapped connectivity rule. Many attractive features of Bi-swapped networks show that the Bi-swapped architecture provides a competitive network scheme for constructing massive parallel computers. In this paper, the minimum dominating set （MDS） problem and the minimum connected dominating set （MCDS） problem in Bi-swapped networks are investigated based on the connectivity rule of these networks. We prove these two problems are NP-hard, and present several simple but efficient approximation algorithms for them based on the modularity feature of Bi-swapped networks. In an N-node Bi-swapped network, the proposed algorithms use as input a given DS or CDS of the factor network, and yield a DS or CDS of the Bi-swapped network with a good performance guarantee provided that the input is a corresponding good DS or CDS for the factor network. By contrast, if we view the Bi-swapped network as a general graph without making use of its modularity feature, finding a DS or CDS with an almost same performance guarantee as the above needs time O（N2）. Besides,by establishing a relationship between （connected） domination numbers of Bi-swapped networks and their factor networks, we derive several nontrivial lower and upper bounds on （connected） domination numbers of Bi-swapped networks. Our work suggests a feasible approach to big data processing and analysis in combinatorial networks such as Bi-swapped networks.

关 键 词：互连网络 Bi-swapped网络 支配集 连通支配集 NP难度 近似算法 

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