低度图的最大团求解算法

• 作者: 王青松 范铁生
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最大团问题 图论 图论算法 NP问题 独立集
• 年，卷（期）: 2010,（6）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 39-41
• 页数: 3页
• 分类号: TP301.6
• 字数: 4273字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2010.06.013

摘要

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d).给出一种求解低度图的最大团的确定性算法.该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题.算法时间复杂度为O(d·n~3).其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	范铁生	辽宁大学信息学院	37	179	7.0	11.0
2	王青松	辽宁大学信息学院	20	83	5.0	9.0