计算机科学与探索 ›› 2013, Vol. 7 ›› Issue (3): 262-271.DOI: 10.3778/j.issn.1673-9418.1208048
胡 新,王丽珍+,何瓦特,姚华传
HU Xin, WANG Lizhen+, HE Wate, YAO Huachuan
摘要: 由于最大团问题(maximum clique problem,MCP)的复杂性、挑战性,以及在数据挖掘等领域的广泛应用,使得求解MCP问题具有非常重要的意义。根据最大团顶点度数较大的特点,提出了从图中第一个度数最大的顶点出发递归求解最大团的算法(简称度数法)。为了进一步提高算法的效率,根据图的特点和最大团的特点提出了三个改进的剪枝策略。从理论上证明了算法的正确性和完整性,其时间复杂度为[O(1.442n)],空间为[O(n2)]。通过实验验证了度数法及其改进剪枝策略的效果和效率。