An O*(3.53(3k))-time parameterized algorithm for the 3-set packing problem Conference Paper

abstract

• A parameterized algorithm for the well-known NP-complete problem 3-set packing is presented. The algorithm is based on the following new approaches: (1) an efficient algorithm for problem instances in which one element is known for each of the 3-sets in a solution packing (i.e., type-1 instances); (2) an efficient algorithm for problem instances in which at least two elements are known for each of the 3-sets in a solution packing (i.e., type-2 instances); and (3) an effective decomposition of a general instance of 3-set packing into two instances of type-1 and type-2, respectively, whose base sets are disjoint. This technique results in an improved parameterized algorithm of running time O*(3.533k) for the 3-set packing problem, improving the previous best upper bound O*(4.613k). 2010 Elsevier B.V. All rights reserved.

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

• Wang, J., Feng, Q., & Chen, J.

citation count

• 4

complete list of authors

• Wang, Jianxin||Feng, Qilong||Chen, Jianer

publication date

• April 2011

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• (n, K)-universal Set
• 3-set Packing
• Divide And Conquer

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2010.12.048

start page

• 1745

end page

• 1753

volume

• 412

issue

• 18

URL

• http://dx.doi.org/10.1016/j.tcs.2010.12.048