度数法求解最大团问题

摘要：

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

关键词：最大团问题(MCP)、顶点度数、NP完全问题

分类号：TP311(计算技术、计算机技术)

在线出版日期：2013-03-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：262-271