顶点加权最大团问题的加权分治算法

Measure and Conquer Approach for the Maximum Vertex Weighted Clique Problem

分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656~np(n)),其中n代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656~np(n))降为O(1.3765~np(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度.

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 analytical method 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~np(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 fromO(1.4656~np(n))to O(1.3765~wp(n))without modifying the algorithm.Our results show that the measure and conquer approach can give more precise time complexity.