Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (2): 50-53.

Previous Articles     Next Articles

Measure and conquer approach for maximum clique problem

ZHI Zhibing, NING Aibing, CHEN Jizhen, WANG Yongfei, YANG Xiaofang   

  1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2016-01-15 Published:2016-01-28

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

支志兵,宁爱兵,陈吉珍,王永斐,杨晓芳   

  1. 上海理工大学 管理学院,上海 200093

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.

null

Key words: branch and reduce, maximum clique problem, measure and conquer, algorithm complexity

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

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