Name
Abstract | ||
|---|---|---|
The paper deals with the classical problem of determining the minimum size of a separating system consisting of sets of size at most k. A set system is said to be a separating system if there are no two elements that are part of exactly the same sets. Separating systems of bounded test size play an important role in the field of group testing and its applications. The first and most important results are due to Katona (1966), who proved a theorem that determines the minimum size n(m,k) of a separating system of k-sets of an underlying set of size m implicitly and also gave lower and upper bounds. Wegener (1979), Luzgin (1980), and Ahlswede (2008) also proved important bounds, however, a closed formula or a fast algorithm to compute n(m,k) has not been known so far. We give a simple, short proof of a stronger version of Katona’s main theorem that also leads to a polynomial algorithm to compute n(m,k). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2019.10.033 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Separating system,k-set,Non-adaptive search,Group testing | Journal | 276 |
Issue | ISSN | Citations |
C | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |
| Eva Hosszu | 2 | 11 | 3.29 |
| János Tapolcai | 3 | 364 | 41.42 |