An improved kernelization algorithm for r-Set Packing

被引：18

作者：

Abu-Khzam, Faisal N. ^{[1
]}

机构：

[1] Lebanese Amer Univ, Dept Comp Sci & Math, New York, NY 10115 USA

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 16期

关键词：

Fixed-parameter algorithms; Kernelization; Crown decomposition; Set Packing; Graph algorithms; PARAMETERIZED ALGORITHM; VERTEX COVER; KERNELS;

D O I：

10.1016/j.ipl.2010.04.020

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a reduction procedure that takes an arbitrary instance of the r-Set Packing problem and produces an equivalent instance whose number of elements is in O(k(r-1)), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：621 / 624

页数：4

共 14 条

[1]

Abu-Khzam FN, 2007, LECT NOTES COMPUT SC, V4619, P434

[2] Crown structures for vertex cover kernelization [J].

Abu-Khzam, Faisal N. ;

Fellows, Michael R. ;

Langston, Michael A. ;

Suters, W. Henry .

THEORY OF COMPUTING SYSTEMS, 2007, 41 (03) :411-430

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[4]

Bodlaender HL, 2008, LECT NOTES COMPUT SC, V5125, P563, DOI 10.1007/978-3-540-70575-8_46

[5] Vertex Cover: Further observations and further improvements [J].

Chen, J ;

Kanj, IA ;

Jia, WJ .

JOURNAL OF ALGORITHMS, 2001, 41 (02) :280-301

[6]

Chor B, 2004, LECT NOTES COMPUT SC, V3353, P257

[7]

DELLHOLGER, 2010, P 42 ACM S IN PRESS

[8]

Downey R. G., 1999, MG COMP SCI

[9]

Fellows MR, 2004, LECT NOTES COMPUT SC, V3221, P311

[10] An efficient parameterized algorithm for m-set packing [J].

Jia, WJ ;

Zhang, CL ;

Chen, J .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 50 (01) :106-117

← 1 2 →