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