A faster parameterized algorithm for set packing

Ioannis Koutis

doi:10.1016/j.ipl.2004.12.005

A faster parameterized algorithm for set packing

Ioannis Koutis

Research output: Contribution to journal › Article › peer-review

37 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	7-9
Number of pages	3
Journal	Information Processing Letters
Volume	94
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2004.12.005
State	Published - Apr 15 2005
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Algorithms
Analysis of algorithms
Parameterized computation
Set packing

Access to Document

10.1016/j.ipl.2004.12.005

Cite this

@article{b9d504267c6c4f0fba2e1c2004624526,

title = "A faster parameterized algorithm for set packing",

abstract = "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].",

keywords = "Algorithms, Analysis of algorithms, Parameterized computation, Set packing",

author = "Ioannis Koutis",

note = "Funding Information: E-mail address: [email protected] (I. Koutis). 1 Supported in part by NSF Grants CCR-9902091, ACI-0086093, and CCR-0122581.",

year = "2005",

month = apr,

day = "15",

doi = "10.1016/j.ipl.2004.12.005",

language = "English (US)",

volume = "94",

pages = "7--9",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A faster parameterized algorithm for set packing

AU - Koutis, Ioannis

N1 - Funding Information: E-mail address: [email protected] (I. Koutis). 1 Supported in part by NSF Grants CCR-9902091, ACI-0086093, and CCR-0122581.

PY - 2005/4/15

Y1 - 2005/4/15

N2 - 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].

AB - 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].

KW - Algorithms

KW - Analysis of algorithms

KW - Parameterized computation

KW - Set packing

UR - http://www.scopus.com/inward/record.url?scp=13844309916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=13844309916&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2004.12.005

DO - 10.1016/j.ipl.2004.12.005

M3 - Article

AN - SCOPUS:13844309916

SN - 0020-0190

VL - 94

SP - 7

EP - 9

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

A faster parameterized algorithm for set packing

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this