一个求解简单超图中最大独立集的算法

• 作者: 刘忠 邵春芳
• 来源期刊: 中国西部科技
• 学科: 数学
• 关键词: 超图 独立集 贪婪横贯 最大独立集 算法
• 年，卷（期）: 2006,（35）
• 所属期刊栏目: 教育园地
• 页码范围: 57
• 页数: 1页
• 分类号: O1
• 字数: 1536字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-6396.2006.35.043

摘要

本文从贪婪横贯求法中得到启示,通过改进得到一种基于贪婪准则的求解有限的简单超图的极大独立集的算法:求出一定数量的极大独立集合,再从中挑出顶点数最多的作为极大独立集合.给出了算法和它的时间复杂度的分析以及正确性的证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘忠	四川建筑职业技术学院计算机工程系	14	114	4.0	10.0
5	邵春芳	四川建筑职业技术学院计算机工程系	3	5	1.0	2.0