An efficient parameterized algorithm for m-set packing uri icon

abstract

  • We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then our algorithm is fixed-parameter tractable. For example, if the size of the sets is bounded by 3, then our algorithm runs in time O((5.7k)kn).

published proceedings

  • Journal of Algorithms

author list (cited authors)

  • Jia, W., Zhang, C., & Chen, J.

citation count

  • 58

complete list of authors

  • Jia, Weijia||Zhang, Chuanlin||Chen, Jianer

publication date

  • January 2004