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

摘要：

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

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

分类号：TP301.5(计算技术、计算机技术)

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

在线出版日期：2016-03-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：50-53