作　　者： ;

机构地区： 广东商学院信息学院

出　　处： 《计算机工程与应用》 2010年第21期9-13,共5页

摘　　要： 定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。 The problem of connected dominating set in digraph is defined.A reduction rule for this problem is designed.Reduction rules can reduce the size of original digraph;then an approximation algorithm is designed to find a connected dominating set in the reduced digraph;finally,optimization rule is used to cut down the size of connected dominating set.Simulations in different random digraphs show that these rules and algorithms are effective.

关 键 词： 连通支配集 有向图 参数算法 规约 近似算法

领　　域： [自动化与计算机技术] [自动化与计算机技术]