期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到3篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
加权3-Set Packing问题的核心化 被引量：1
1
作者 李绍华 冯启龙 +1 位作者 王建新 陈建二 《计算机研究与发展》 EI CSCD 北大核心 2012年第8期1781-1786,共6页
Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定... Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-SetPacking问题大小为27k3-36k2+12k的核,该核心化结果是加权3-SetPacking问题的首个核心化结果.得到的加权3-SetPacking的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核. 展开更多
关键词 加权3-set packing 加权3D-Matching 核心化 局部简化 参数算法
在线阅读 下载PDF
加权3-Set Packing的改进算法 被引量：1
2
作者 冯启龙 王建新 陈建二 《软件学报》 EI CSCD 北大核心 2010年第5期886-898,共13页
Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Co... Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k). 展开更多
关键词 加权3-setpacking 加权3-setpacking augmentation color-coding
在线阅读 下载PDF
3-Set Packing参数化计数问题的复杂性及近似算法
3
作者 刘运龙 《计算机科学》 CSCD 北大核心 2016年第9期23-26,共4页
3-Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matchin... 3-Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。 展开更多
关键词 3-set packing 计数 复杂性 近似算法
在线阅读 下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部