Set packing
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/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 。