加权最小顶点覆盖的加权分治算法

Measure and Conquer Algorithm for Minimum Weighted Vertex Cover Problem

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性.

The measure and conquer approach is a new technique for algorithm design and analysis. The approach is based on the definition of a suitable measure of the subproblems, so as to obtain the best running time in the worst case. minimum Weighted Vertex cover problem is a typical NP-hard problem. In this paper,a fast recursive algorithm based on the branch and reduce technology is designed. Then,the measure and conquer approach is used to analyze the algorithm, and proves that the running time of the algorithm is O （ 1. 3482^np （ n ） ）, where p （ n ） is the polynomial function of node number n of the problem. Contrastive analysis shows that the running time of this approach is lower than that of the traditional approach.