有向图连通支配集求解算法

作     者：高文宇 GAO Wen-yu

作者机构：广东商学院信息学院广州510320 

基　　金：广东省自然科学基金No.8151032001000013~~ 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2010年第46卷第21期

页      码：9-13页

摘      要：定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1002-8331.2010.21.003

馆 藏 号：203518280...