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

Measure and conquer approach for maximum clique problem

作　　者：支志兵 宁爱兵[1] 陈吉珍 王永斐 杨晓芳[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程与应用》2016年第2期50-53,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.51008196);上海市一流学科建设项目资助(No.XTKX2012)

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

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

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]