| 有向图连通支配集求解算法 |
| |
| 引用本文： | 高文宇.有向图连通支配集求解算法[J].计算机工程与应用,2010,46(21):9-13. |
| |
| 作者姓名： | 高文宇 |
| |
| 作者单位： | 广东商学院,信息学院,广州,510320 |
| |
| 摘 要： | 定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则，通过规约规则的实施来降低原问题的规模；随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集；最后结合规约规则带来的一些良好特性设计了优化规则，通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。
|
| 关 键 词： | 连通支配集 有向图 参数算法 规约 近似算法 |
| 收稿时间： | 2010-4-26 |
| 修稿时间： | 2010-6-10
|
Algorithm of digraph connected dominating set |
| |
| GAO Wen-yu.Algorithm of digraph connected dominating set[J].Computer Engineering and Applications,2010,46(21):9-13. |
| |
| Authors: | GAO Wen-yu |
| |
| Affiliation: | GAO Wen-yu (School of Information Science,Guangdong University of Business Studies,Guangzhou 510320,China ) |
| |
| Abstract: | 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. |
| |
| Keywords: | connected dominating set digraph parameterized algorithm reduction approximation |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
