论文部分内容阅读
Packing和Matching问题是一类重要的NP难解问题，该类问题的参数算法和核心化研究受到了人们广泛的关注．主要研究了加权3-SetPacking的核心化算法．对于加权3-SetPacking问题，基于对问题结构的深入分析，提出并证明了2个简化规则．首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数，然后在限定问题实例中包含1个给定元素的集合的个数．基于对集合个数的限定，得到问题实例中总的集合个数的上界．并基于上述性质得到2个简化规则，可得到加权3-SetPacking问题大