The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection 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...The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection 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 O (f(k,m)+g(k,m)n), where where, bm is the minimal positive root of m-degree equation and e= =2.7182818. In particular, this gives an O (k4(5.7k)k+[k(5.7k)k+3]n) algorithm to construct mutually k disjoint sets if |c|≤3 for any c∈C.展开更多
基金the Main Subject Foundation of the State Council's Office of OverseasChinese Affairs under Grant 93A109. Part of the work was
文摘The PARAMETERIZED SET PACKING problem asks, for an input consisting of a col- lection 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 O (f(k,m)+g(k,m)n), where where, bm is the minimal positive root of m-degree equation and e= =2.7182818. In particular, this gives an O (k4(5.7k)k+[k(5.7k)k+3]n) algorithm to construct mutually k disjoint sets if |c|≤3 for any c∈C.
