论文部分内容阅读
图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起来.Bi-swapped网络的优良特性使得它可为构建并行计算机提供潜在有竞争力的体系结构方案.文中基于Bi-swapped网络的互连规则研究Bi-swapped网络中最小支配集问题和最小连通支配集问题.首先证明这两个问题都是NP难度的,然后基于Bi-swapped网络的模块