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 -