Name
Abstract | ||
|---|---|---|
In combinatorial group testing problems the questioner needs to find a special element (x [n]) by testing subsets of [n]. Tapolcai et al. (in: Proceedings of IEEE INFOCOM, Toronto, Canada, pp 1860–1868, 2014; IEEE Trans Commun 64(6):2527–2538, 2016) introduced a new model, where each element knows the answer for those queries that contain it and each element should be able to identify the special one. Using classical results of extremal set theory we prove that if (mathcal {F}_n subseteq 2^{[n]}) solves the non-adaptive version of this problem and has minimal cardinality, then $$begin{aligned} lim _{n rightarrow infty } frac{|mathcal {F}_n|}{log _2 n} = log _{(3/2)}2. end{aligned}$$This improves results in Tapolcai et al. (2014, 2016). We also consider related models inspired by secret sharing models, where the elements should share information among them to find out the special one. Finally the adaptive versions of the different models are investigated. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s10878-018-0248-z | J. Comb. Optim. |
Keywords | Field | DocType |
Combinatorial group testing,Non-adaptive,Information sharing | Set theory,Combinatorics,Combinatorial group testing,Secret sharing,Cardinality,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 4 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Máté Vizer | 2 | 27 | 14.06 |