On the Power of Additive Combinatorial Search Model

Vladimir Grebinski (1)

1 POLKA - Polynomials, Combinatorics, Arithmetic

We consider two generic problems of combinatorial search under the additive model. The first one is the problem of reconstructing bounded--weight vectors. We establish an optimal upper bound and observe that it unifies many known results for coin--weighing problems. The developed technique provides a basis for the graph reconstruction problem. Optimal upper bound is proven for the class of $k$--degenerate graphs.

Mots clés: group testing; recherche combinatoire; combinatorial search; coin weighing; problème de pesage

Domaines: Autre [cs.OH]

Vladimir Grebinski. On the Power of Additive Combinatorial Search Model. Fourth Annual International Computing and Combinatorics Conference - COCOON'98, 1998, Taipei/Taiwan, pp.194-203. ⟨inria-00098615⟩