TY - JOUR

T1 - Compactors for parameterized counting problems

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2020 Elsevier Inc.

PY - 2021/2

Y1 - 2021/2

N2 - The concept of compactor has been introduced in Kim et al. (2018) as a general data-reduction concept for parametrized counting problems. For a function F: ς → N and a parameterization κ: ς → N a compactor (C, E) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M P. If the size of P (x) is bounded by a polynomial function of κ (x), then we say that the compactor (C, E) is of polynomial size. Compactors can be seen as an attempt to formalize the notion of preprocessing for counting problems.

AB - The concept of compactor has been introduced in Kim et al. (2018) as a general data-reduction concept for parametrized counting problems. For a function F: ς → N and a parameterization κ: ς → N a compactor (C, E) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M P. If the size of P (x) is bounded by a polynomial function of κ (x), then we say that the compactor (C, E) is of polynomial size. Compactors can be seen as an attempt to formalize the notion of preprocessing for counting problems.

KW - Compactor

KW - Counting algorithms

KW - Graph Algorithms

KW - Parameterized algorithms

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

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

U2 - 10.1016/j.cosrev.2020.100344

DO - 10.1016/j.cosrev.2020.100344

M3 - Review article

AN - SCOPUS:85101442165

SN - 1574-0137

VL - 39

JO - Computer Science Review

JF - Computer Science Review

M1 - 100344

ER -