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

doi:10.3778/j.issn.1002-8331.2010.21.003

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (21): 9-13.DOI: 10.3778/j.issn.1002-8331.2010.21.003

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

高文宇

广东商学院信息学院，广州 510320

收稿日期:2010-04-26 修回日期:2010-06-10 出版日期:2010-07-21 发布日期:2010-07-21
通讯作者: 高文宇

Algorithm of digraph connected dominating set

GAO Wen-yu

School of Information Science，Guangdong University of Business Studies，Guangzhou 510320，China

Received:2010-04-26 Revised:2010-06-10 Online:2010-07-21 Published:2010-07-21
Contact: GAO Wen-yu

摘要/Abstract

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

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

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.

Key words: connected dominating set, digraph, parameterized algorithm, reduction, approximation

中图分类号:

TP301.6

高文宇. 有向图连通支配集求解算法[J]. 计算机工程与应用, 2010, 46(21): 9-13.

GAO Wen-yu. Algorithm of digraph connected dominating set[J]. Computer Engineering and Applications, 2010, 46(21): 9-13.

[1]	李振涛，冯元珍，王正新. 事件触发下多智能体系统固定时间二分一致性[J]. 计算机工程与应用, 2021, 57(21): 80-86.
[2]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[3]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[4]	陈恒1，2，李冠宇2，孙云浩2. 重排序RDF流三元组模式的蚁群优化方法[J]. 计算机工程与应用, 2017, 53(12): 172-177.
[5]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[6]	杜立智. 一个可行的RSA密码破译方法[J]. 计算机工程与应用, 2016, 52(14): 119-124.
[7]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[8]	辛强伟. 基于最小连通支配集的无线传感器网络容错研究[J]. 计算机工程与应用, 2015, 51(11): 18-21.
[9]	刘敏娜，解争龙，黄素萍. 基于任务图的并行调度MEWFM算法[J]. 计算机工程与应用, 2015, 51(10): 67-71.
[10]	耿显亚，许峰. 基于图论模型的一类集成电路布线算法[J]. 计算机工程与应用, 2015, 51(1): 21-25.
[11]	袁津生，毛新武. 基于组合特征的中文新闻网页关键词提取方法[J]. 计算机工程与应用, 2014, 50(19): 222-226.
[12]	高东，许欣，马昕，张贝克. 基于符号有向图与趋势分析的故障诊断框架[J]. 计算机工程与应用, 2014, 50(13): 6-9.
[13]	佟超，王建新，齐建东. 基于形式化规约的缺陷规则库构建与检测方法[J]. 计算机工程与应用, 2014, 50(13): 66-72.
[14]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[15]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.

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

Algorithm of digraph connected dominating set

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics