A fixed-parameter-tractable algorithm for set packing期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

A fixed-parameter-tractable algorithm for set packing

Authors:

Affiliation:

(1) Department of Mathematics, Jinan University, 510632 Guangzhou, China;(2) Department of Computer Science, City University of Hong Kong, Hong Kong, China;(3) Department of Computer Science, Texas A&M University, 77843-3112 College Station, TX, U.S.A.

Abstract:

The PARAMETERIZED SET PACKING problem asks, for an input consisting of a collectionC ofn finite sets with |c|≤m for anyc∈C and a positive integerk, whetherC contains at leastk 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

$\begin{gathered} f(k,m) = (m - 2)\sqrt {m - 1} k^4 \left {\frac{{k^{m - 2} (m - 1)^{m - 1} b_m }}{{e^{m - 2} }}} \right]^k , \hfill \\ g(k,m) = (m + 1)(m - 2)k\sqrt {m - 1} \left {\frac{{k^{m - 2} (m - 1)^{m - 1} b_m }}{{e^{m - 2} }}} \right]^k + m \hfill \\ \end{gathered}$

, where,b _m is the minimal positive root ofm-degree equation

$x^m = \sum\limits_{i = 1}^{m - 1} {(\mathop i\limits^m )x^{m - i} }$

and $e = \sum\limits_{i = 0}^{ + \infty } {\frac{1}{{i!}} = 2.7182818}$ . In particular, this gives an O (k ⁴(5.7k)^k+k(5.7k)^k+3]n) algorithm to construct mutuallyk disjoint sets if |c|≤3 for anyc∈C. This work is supported partly by the Main Subject Foundation of the State Council's Office of Overseas Chinese Affairs under Grant 93A109. Part of the work was done while this author was visiting City University of Hong Kong. This work is supported partly by UGC of Hong Kong under Grant 7000853. This work is supported partly by the National Science Foundation under Grant CCR-9613805.

Keywords:

Set packing fixed-parameter-tractable algorithm

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏