论文研究有向图连通支配集求解算法.pdf

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