%0 Journal Article
%T 加权3-setpacking的改进算法
%A 冯启龙？
%A 王建新？
%A 陈建二？
%J 软件学报
%P 886-898
%D 2010
%X packing问题构成了一类重要的np难问题.对于加权3-setpacking问题,把问题转化成加权3-setpackingaugmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合color-coding技术,首先给出了一种时间复杂度为o*(10.63k)的参数算法,极大地改进了目前文献中的最好结果o*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到o*(7.563k).
%K 加权3-set
%K packing
%K 加权3-set
%K packing
%K augmentation
%K color-coding
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3524&flag=1