Covering and packing in linear space

Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto

doi:10.1016/j.ipl.2011.08.002

Covering and packing in linear space

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

Here, we introduce a new, fast zeta transform algorithm that improves the space requirement to only linear in the size of the given set family, while not increasing the time requirement

Original language	English
Journal	Information Processing Letters
Volume	111
Issue number	21-22
Pages (from-to)	1033
Number of pages	3
ISSN	0020-0190
DOIs	https://doi.org/10.1016/j.ipl.2011.08.002
Publication status	Published - 2011

Keywords

Algorithms
Chromatic polynomial
Zeta transform

Access to Document

10.1016/j.ipl.2011.08.002

Cite this

@article{0ff3386dd2d54169a94b05da126f874b,

title = "Covering and packing in linear space",

abstract = "Here, we introduce a new, fast zeta transform algorithm that improves the space requirement to only linear in the size of the given set family, while not increasing the time requirement",

keywords = "Algorithms, Chromatic polynomial, Zeta transform, Algorithms, Chromatic polynomial, Zeta transform",

author = "Andreas Bj{\"o}rklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto",

note = "Ikke dublet",

year = "2011",

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

language = "English",

volume = "111",

pages = "1033",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "21-22",

}

TY - JOUR

T1 - Covering and packing in linear space

AU - Björklund, Andreas

AU - Husfeldt, Thore

AU - Kaski, Petteri

AU - Koivisto, Mikko

N1 - Ikke dublet

PY - 2011

Y1 - 2011

N2 - Here, we introduce a new, fast zeta transform algorithm that improves the space requirement to only linear in the size of the given set family, while not increasing the time requirement

AB - Here, we introduce a new, fast zeta transform algorithm that improves the space requirement to only linear in the size of the given set family, while not increasing the time requirement

KW - Algorithms

KW - Chromatic polynomial

KW - Zeta transform

KW - Algorithms

KW - Chromatic polynomial

KW - Zeta transform

U2 - 10.1016/j.ipl.2011.08.002

DO - 10.1016/j.ipl.2011.08.002

M3 - Journal article

SN - 0020-0190

VL - 111

SP - 1033

JO - Information Processing Letters

JF - Information Processing Letters

IS - 21-22

ER -

Covering and packing in linear space

Abstract

Keywords

Access to Document

Fingerprint

Cite this