-
题名最大团问题的加权分治算法
被引量：7
- 1
-
-
作者
支志兵
宁爱兵
陈吉珍
王永斐
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2016年第2期50-53,共4页
-
基金
国家自然科学基金(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））。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。
-
关键词
分支降阶
最大团问题
加权分治
算法复杂性
-
Keywords
branch and reduce
maximum clique problem
measure and conquer
algorithm complexity
-
分类号
TP301.5
[自动化与计算机技术—计算机系统结构]
-
-
题名最小顶点覆盖问题的加权分治算法
被引量：5
- 2
-
-
作者
陈吉珍
宁爱兵
支志兵
王永斐
张惠珍
-
机构
上海理工大学管理学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2015年第5期151-155,共5页
-
基金
国家自然科学基金(71401106)
上海市一流学科建设项目资助(S1201YLXK)
高等学校博士学科点专项科研基金联合资助课题(20123120120005)
-
文摘
最小顶点覆盖问题是组合优化中经典NP—Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O（1．255n），优于常规分析下的时间复杂度O（1．325n）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。
-
关键词
图论
算法复杂性
加权分治技术
分支降阶技术
最小顶点覆盖
-
Keywords
graph theory
algorithm complexity
Measure and Conquer
Bbranch and Reduce
Minimum Vertex covey
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名Perfect Code问题的加权分治算法
被引量：2
- 3
-
-
作者
王英磊
宁爱兵
支志兵
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第3期594-596,共3页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科建设项目(XTKX2012)资助
-
文摘
加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂度更好的精确算法.Perfect Code问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂度为O(1.3248np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂度低于采用传统方法得到的时间复杂度.
-
关键词
加权分治技术
PERFECT
Code问题
分支降阶技术
算法复杂性
-
Keywords
measure and conquer
perfect code problem
branch and reduce technology
algorithm complexity
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名图论中最大独立集问题的精确算法
被引量：2
- 4
-
-
作者
陈吉珍
宁爱兵
支志兵
胡琳琳
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机工程与应用》
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
[理学—运筹学与控制论]
-
-
题名3度图的最小顶点覆盖问题的多项式时间算法
- 5
-
-
作者
支志兵
宁爱兵
胡琳琳
张惠珍
-
机构
上海理工大学管理学院
-
出处
《数学理论与应用》
2014年第3期114-120,共7页
-
基金
国家自然科学基金(71401106)
上海市一流学科建设项目资助(S1201YLXK)
高等学校博士学科点专项科研基金联合资助课题(20123120120005)
-
文摘
最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.
-
关键词
最小顶点覆盖
多项式时间算法
-
Keywords
Minimum vertex cover Polynomial time algorithm
-
分类号
O157
[理学—数学]
-
-
题名删除顶点生成二分图问题的精确算法
- 6
-
-
作者
支志兵
宁爱兵
熊小华
王永斐
陈吉珍
杨晓芳
-
机构
上海理工大学管理学院
上海第二工业大学计算机与信息学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第9期2122-2125,共4页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科建设项目(XTKX2012)资助
-
文摘
分支降阶是目前广泛用于设计精确算法求解NP-Hard问题的技术之一,该技术主要通过快速降阶、分支及递归求解原问题及其子问题.为了降低分支降阶算法的时间复杂度,一方面可以增加降阶规则、改变算法的设计思想;另一方面可以运用更精确的时间复杂度分析方法分析算法.本文针对删除最少顶点生成二分图问题,首先运用常规枚举方法得到一个时间复杂度为O(3n)的算法;然后通过增加降阶规则、改善算法设计和运用加权分治技术分析算法等方法,最终得到一个时间复杂度为O(1.8157n)的精确算法.本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的.
-
关键词
删除顶点生成二分图
精确算法
分支降阶技术
加权分治技术
-
Keywords
odd cycle transversals
exact algorithm
branch and reduce
measure and conquer approach
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名瓶颈Steiner树问题的降阶分支限界算法
- 7
-
-
作者
宁爱兵
刘艳芳
支志兵
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第5期1124-1127,共4页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科项目(XTKX2012)资助
-
文摘
瓶颈Steiner树问题是经典的组合优化问题,是一个NP难题,在生物网络、交通运输网络、电路设计以及计算机网络布局等领域内有着广泛的应用.本文首先研究瓶颈Steiner树的数学性质,这些数学性质不仅可以判断某些点和边一定在某个最优瓶颈Steiner树中,还可以判断某些点和边一定不在某个最优瓶颈Steiner树中,从而达到降低问题规模和求解难度的目的.然后在瓶颈最小生成树是多项式可解的基础上,提出能快速求解瓶颈Steiner树的降阶分支限界算法.另外文中还通过对多个示例进行分析和求解来阐述算法的原理和过程.
-
关键词
瓶颈Steiner树
瓶颈最小生成树
降阶
分支限界算法
-
Keywords
bottleneck steiner tree problem
minimum bottleneck spanning tree
reduction
branch and bound algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名容斥原理在汉密尔顿问题中的应用
- 8
-
-
作者
支志兵
-
机构
上海理工大学管理学院
-
出处
《数学理论与应用》
2014年第2期118-123,共6页
-
基金
上海市一流学科建设项目资助(XTKX2012)
-
文摘
容斥原理是组合数学中的经典的计数方法,该原理的基本思想是:先不排除重叠的情况,把包含于某种性质的所有对象的数目先计算出来,然后再把重复计算的数目排斥出去.针对汉密尔顿问题,[15]利用邻接矩阵给出了判断一个图是否为汉密尔顿图的充要条件.本文将结合容斥原理给出汉密尔顿路径存在性的一个判别条件,并给出汉密尔顿路径的计算公式.
-
关键词
容斥原理
邻接矩阵
汉密尔顿问题
-
Keywords
The inclusion- exclusion principle Adjacency matrix The Hamilton problem
-
分类号
O157
[理学—数学]
-
