A faster parameterized algorithm for set packing

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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(2O(t)nNlogN). For the special case of sets of bounded size, this improves the O((ck)kn) algorithm of Jia et al. [J. Algorithms 50 (1) (2004) 106].

Original languageEnglish (US)
Pages (from-to)7-9
Number of pages3
JournalInformation Processing Letters
Volume94
Issue number1
DOIs
StatePublished - Apr 15 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Algorithms
  • Analysis of algorithms
  • Parameterized computation
  • Set packing

Fingerprint Dive into the research topics of 'A faster parameterized algorithm for set packing'. Together they form a unique fingerprint.

Cite this