加权3D-Matching的改进算法

来源 :计算机研究与发展 | 被引量 : 0次 | 上传用户：yaya_tush

【摘要】

：

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权

【作者】

：

冯启龙王建新陈建二

【机构】

：

中南大学信息科学与工程学院

【出处】

：

计算机研究与发展

【发表日期】

：

2009年11期

【关键词】

：

加权3D-matching 加权3D-matching augmentation color-coding 动态规划参数计算 weighted 3D -mat

【基金项目】

：

基金项目：国家“九七三”重点基础研究发展计划前期研究专项基金项目（2008CB317107）,国家自然科学基金项目（60773111,60873265）,长江学者和创新团队发展计划基金项目（IRT0661）

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的（k＋1）-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质：k-matching中存在2列使得该2列至少有2k/3元素被包含在（k＋1）

其他文献

双重预防机制构建中海事安全监管责任辨析

风险管控和隐患排查治理是防范遏制重特大事故构建双重预防机制的核心内容,也是水上交通事故预防预控的重点.文章从依法行政的角度,对风险防控与事故隐患排查治理体系中主体

期刊

风险防控隐患排查安全监管

构架军地“连心桥”

【正】走近"最可爱的人""砰砰……叭叭……",66455部队即将转业的干部国佩军以近乎完美的动作完成了运动射击、攀越障碍、擒拿格斗等军事科目,精彩的演示赢得了在场观众热烈

期刊