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

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