A faster parameterized algorithm for set packing

被引：35

作者：

Koutis, I ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 94卷 / 01期

基金：

美国国家科学基金会;

关键词：

algorithms; analysis of algorithms; parameterized computation; set packing;

D O I：

10.1016/j.ipl.2004.12.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an efficient parameterized algorithm for the (k, t)-set packing problem, in which we are looking for a collection of k disjoint sets whose union consists of t elements. The complexity of the algorithm is O(2(O(t))nN log N). For the special case of sets of bounded size, this improves the O((ck)(k)n) algorithm of Jia et al. (c) 2004 Elsevier B.V. All rights reserved.

引用

页码：7 / 9

页数：3