An efficient parameterized algorithm for m-set packing

被引：36

作者：

Jia, WJ ^{[1
]}

Zhang, CL

Chen, J

机构：

[1] City Univ Hong Kong, Dept Comp Engn & IT, Hong Kong, Hong Kong, Peoples R China

[2] Jinan Univ, Dept Math, Guangzhou 510632, Peoples R China

[3] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 50卷 / 01期

基金：

美国国家科学基金会;

关键词：

parameterized computation; set packing; exact algorithm; NP-hard problem;

D O I：

10.1016/j.jalgor.2003.07.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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)(k)n). (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：106 / 117

页数：12

共 12 条

[1]

[Anonymous], 1976, GRAPH THEORY APPL

[2]

[Anonymous], 1994, FDN COMPUTER SCI

[3] An improved fixed-parameter algorithm for vertex cover [J].

Balasubramanian, R ;

Fellows, MR ;

Raman, V .

INFORMATION PROCESSING LETTERS, 1998, 65 (03) :163-168

[4] ON THE STRUCTURE OF PARAMETERIZED PROBLEMS IN NP [J].

CAI, LM ;

CHEN, J ;

DOWNEY, R ;

FELLOWS, M .

INFORMATION AND COMPUTATION, 1995, 123 (01) :38-49

[5] On fixed-parameter tractability and approximability of NP optimization problems [J].

Cai, LM ;

Chen, JN .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (03) :465-474

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

Chen, J ;

Kanj, IA ;

Jia, WJ .

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

[7]

Chen J., 2001, LECT NOTES COMPUTER, V2245, P120

[8]

DOWNEY R, 1999, PARAMETERIZED COMPLE

[9]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019

[10]

Karp R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9

← 1 2 →