加权分治与皇冠技术求解最大加权独立集

摘要：

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度.针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集.首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法.

关键词：皇冠分解、加就权独立集、加权分治算法、分支降阶

所属期刊栏目：53

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

资助基金：国家自然科学基金71401106;上海市一流学科建设项目S1201YLXK;高等学校博士学科点专项科研基金联合资助课题20123120120005

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

页数：共6页

页码：26-30,110