Name
Abstract | ||
|---|---|---|
Roughly speaking, an (n, (r, s))-Cover Free Family (CFF) is a small set of n-bit strings such that: "in any d := r+s indices we see all patterns of weight r". CFFs have been of interest for a long time both in discrete mathematics as part of block design theory, and in theoretical computer science where they have found a variety of applications, for example, in parametrized algorithms where they were introduced in the recent breakthrough work of Fomin, Lokshtanov and Saurabh [16] under the name 'lopsided universal sets'. In this paper we give the first explicit construction of cover-free families of optimal size up to lower order multiplicative terms, for any r and s. In fact, our construction time is almost linear in the size of the family. Before our work, such a result existed only for r = d degrees((1)), and r = omega (d/(log log d log log log d)). As a sample application, we improve the running times of parameterized algorithms from the recent work of Gabizon, Lokshtanov and Pilipczuk [18]. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-57586-5_13 | ALGORITHMS AND COMPLEXITY (CIAC 2017) |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Parametrization,Multiplicative function,Block design,Omega,Small set,Mathematics,Parameterized algorithms,Universal set | Journal | 10236 |
ISSN | Citations | PageRank |
0302-9743 | 7 | 0.48 |
References | Authors | |
24 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nader H. Bshouty | 1 | 1171 | 126.09 |
| Ariel Gabizon | 2 | 156 | 13.97 |