Abstract:

Branching and order-reducing are widely used for solving NP-Hard Problems.The main idea of the approach is to solve the problem by decomposing it into two or more sub-problems,and the sub-problems can be recursively solved.But we cannot get a better result by using the normal complexity analyticalmethod since it is not so accurate.The measure and conquer approach is a new technique for algorithm design and complexity analysis.This paper designs an algorithm to solve the weighted maximum clique problem and uses traditional analysis technology to analyze the worst-case running time of the algorithm and gets O(1.4656ⁿp(n))running time,where p(n)is the polynomial function of node number nin the problem.We employ the measure and conquer approach to improve the time complexity of the algorithm from O(1.4656ⁿp(n)) to O (1.3765ⁿp(n))without modifying the algorithm. Our results show that the measure and conquer approach can give more precise time complexity.

Key words:

Branching and order-reducing algorithm, Weighted maximum clique, Time complexity, Measure and conquer, Graph theory