A faster parameterized algorithm for set packing

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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
Issue number1
StatePublished - Apr 15 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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


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

Cite this