度数法求解最大团问题

• 作者: 何瓦特 姚华传 王丽珍 胡新
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 最大团问题(MCP) 顶点度数 NP完全问题
• 年，卷（期）: 2013,（3）
• 页码范围: 262-271
• 分类号: TP311
• 字数: 7483字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1208048

摘要

由于最大团问题(maximum clique problem,MCP)的复杂性、挑战性,以及在数据挖掘等领域的广泛应用,使得求解MCP问题具有非常重要的意义.根据最大团顶点度数较大的特点,提出了从图中第一个度数最大的顶点出发递归求解最大团的算法(简称度数法).为了进一步提高算法的效率,根据图的特点和最大团的特点提出了三个改进的剪枝策略.从理论上证明了算法的正确性和完整性,其时间复杂度为 O(1.442n),空间为 O(n2).通过实验验证了度数法及其改进剪枝策略的效果和效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王丽珍	云南大学信息学院计算机科学与工程系	110	1069	18.0	27.0
2	姚华传	云南大学信息学院计算机科学与工程系	6	18	2.0	4.0
3	何瓦特	云南大学信息学院计算机科学与工程系	10	24	3.0	4.0
4	胡新	云南大学信息学院计算机科学与工程系	3	17	2.0	3.0