Chuan Lin ZHANG , Wei Jia JIA , Jian Er CHEN
应用数学学报(英文版). 2001, 17(4): 494-502.
The PARAMETERIZED SET PACKING problem asks,for an input consisting of a collection C of n finite sets with |c|≤m for any c∈C and a positive integer k,whether C contains at least k mutually disjoint sets.We give a fixed-parameter-tractable algorithm for this problem that runs in times ○(f(k,m)+g(k,m)n),where f(k,m)=(m-2)〖KF(〗m-1〖KF)〗k~4〖JB([〗〖SX(〗k~(m-2)(m-1)~(m-1)b_m〖〗e~(m-2)〖SX)〗〖JB)]〗~k,g(k,m)=(m+1)(m-2)k〖KF(〗m-1〖KF)〗〖JB([〗〖SX(〗k~(m-2)(m-1)~(m-1)b_m〖〗e~(m-2)〖SX)〗〖JB)]〗~k+m,where,b_m is the minimal positive root of m-degree equation x~m=∑〖DD(〗m-1〖〗i=1〖DD)〗(〖SX(B〗m〖〗i〖SX)〗)x~(m-i) and e=∑〖DD(〗+∞〖〗i=0〖DD)〗〖SX(〗1〖〗i!〖SX)〗=2.7182818.In particular,this gives an ○(k~4(5.7k)~k+[k(5.7k)~k+3]n) algorithm to construct mutually k disjoint sets if {c}≤3 for any c∈C.