Abstract: Branch and reduce is a widely used approach for solving combinatorial optimization problems. The main idea of the approach is to solve the problem by decomposing it into two or more subproblems, and the subproblems are recursively solved. The measure and conquer approach is a new technique for algorithm design and complexity analysis. This paper designs an algorithm to solve the maximum clique problem. This paper uses traditional analysis technology to analyze the worst-case running time of the algorithm and gets [O(1.380np(n))] running time, where [p(n)] is the polynomial function of node number [n] of the problem. This paper employs the measure and conquer approach to improve the time-complexity of the algorithm from [O(1.380np(n))] to [O(1.325np(n))] without modifying the algorithm. The results of this paper show that measure and conquer approach has tremendous impact on the worst-case running time of the algorithm.

Key words: branch and reduce, maximum clique problem, measure and conquer, algorithm complexity

摘要： 分支降阶是目前广泛用于求解组合优化领域中难题的技术之一，该技术的核心思想是将原问题分支成若干个子问题，并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析，得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析，将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。

关键词: 分支降阶, 最大团问题, 加权分治, 算法复杂性