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

• 作者: 高文宇
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 连通支配集 有向图 参数算法 规约 近似算法
• 年，卷（期）: 2010,（21）
• 页码范围: 9-13
• 分类号: TP301.6
• 字数: 7229字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.21.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高文宇	广东商学院信息学院	19	173	7.0	12.0