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

Computer Science

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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

Originalsprog	Engelsk
Tidsskrift	Information Processing Letters
Vol/bind	111
Udgave nummer	21-22
Sider (fra-til)	1033
Antal sider	3
ISSN	0020-0190
DOI	https://doi.org/10.1016/j.ipl.2011.08.002
Status	Udgivet - 2011

Adgang til dokumentet

10.1016/j.ipl.2011.08.002

Citationsformater

@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",

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

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

Adgang til dokumentet

Fingeraftryk

Citationsformater