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

摘要：

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

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

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省自然科学基金the Natural Science Foundation of Guangdong Province of China under Grant 8151032001000013

在线出版日期：2010-11-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：9-13