| 带权Matching和Packing问题的一种固定参数可解算法 |
| |
| 引用本文： | 刘运龙,陈建二,王建新.带权Matching和Packing问题的一种固定参数可解算法[J].小型微型计算机系统,2008,29(4):672-677. |
| |
| 作者姓名： | 刘运龙 陈建二 王建新 |
| |
| 作者单位： | 1. 中南大学,信息科学与工程学院,湖南,长沙,410083;湖南师范大学,继续教育学院,湖南,长沙,410012
2. 中南大学,信息科学与工程学院,湖南,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金
,
教育部跨世纪优秀人才培养计划 |
| |
| 摘 要： | 带权的m-D MATCHING和m-SET PACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SET PACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法, 接着在此基础上利用问题本身的结构特点对带权的m-D MATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SET PACKING问题和带权的m-D MATCHING问题都是固定参数可解的.
|
| 关 键 词： | 带权m-SET PACKING 带权m-D MATCHING 着色 固定参数可解 带权 Matching Packing 问题设计 定参数 近似算法 Problems Weighted 结构特点 利用 复杂度 时间 规划技术 动态 着色技术 运用 参数化 计算理论 求解 PACKING |
| 文章编号： | 1000-1220(2008)04-0672-06 |
| 修稿时间： | 2006年11月27 |
Fixed-parameter Tractable Algorithms for Weighted Matching and Packing Problems |
| |
| LIU Yun-long,CHEN Jian-er,WANG Jian-xin.Fixed-parameter Tractable Algorithms for Weighted Matching and Packing Problems[J].Mini-micro Systems,2008,29(4):672-677. |
| |
| Authors: | LIU Yun-long CHEN Jian-er WANG Jian-xin |
| |
| Affiliation: | LIU Yun-long1,2,CHEN Jian-er1,WANG Jian-xin1 1(College of Information Science , Engineering,Central South University,Changsha 410083,China) 2(School of Further Education,Hunan Normal University,Changsha 410012,China) |
| |
| Abstract: | |
| |
| Keywords: | weighted m-SET PACKING weighted m-D MATCHING color-coding fixed-parameter tractable |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
