-
题名图论中最大独立集问题的精确算法
被引量：2
- 1
-
-
作者
陈吉珍
宁爱兵
支志兵
胡琳琳
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2016年第1期20-22,109,共4页
-
基金
国家自然科学基金(No.71401106)
上海市一流学科建设项目(No.S1201YLXK)
高等学校博士学科点专项科研基金联合资助课题(No.20123120120005)
-
文摘
独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为O（1.285-n）的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。
-
关键词
图论
最小顶点覆盖
快速降阶
精确算法
-
Keywords
graph theory
maximum independent set
branch and reduce
exact algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名0/1背包问题快速降价法及其应用
被引量：9
- 2
-
-
作者
宁爱兵
马良
-
机构
上海理工大学管理学院
-
出处
《系统工程理论方法应用》
北大核心
2005年第4期372-375,共4页
-
基金
国家自然科学基金资助项目(70471065)
上海市教委重点学科建设资助项目
-
文摘
用数学方法分析了0/1背包问题的特性,提出了一个快速降价算法,该算法能成批确定一定在最优解中的物品和成批排除一定不在最优解中的物品。该算法既可单独使用,又可与启发式算法结合达到更好的结果。文中给出了应用实例及其分析。
-
关键词
0/1背包问题
快速降阶算法
上界
下界
-
Keywords
0/1-knapsack problem
quick reduction algorithm
upper bound
lower bound
-
分类号
O223
[理学—运筹学与控制论]
-
