基于加权分治技术的set packing精确算法

作     者：李绍华 王建新 马振宇 陈建二 

作者机构：中南大学信息科学与工程学院湖南长沙410083 广东商学院信息学院广东广州510320 

基　　金：国家"九七三"重点基础研究前期研究专项项目(2008CB317107)资助 国家自然科学基金项目(60433020 60773111)资助 新世纪优秀人才支持计划项目(NCET-05-083)资助 国家教育部创新团队资助项目(IRT0661)资助 

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2010年第31卷第6期

页      码：1180-1184页

摘      要：加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.setpacking问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的setpacking问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N)的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.

主 题 词：加权分治 set packing问题 最大独立集 精确算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203373247...