最小连通支配集问题的化简算法

• 作者: 高文宇
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最小连通支配集 化简 参数算法 复杂性
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 55-57
• 分类号: TP311.52
• 字数: 3707字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2011.10.018

摘要

分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则.规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模.从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性.

作者信息

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