查看文章

Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form “Does a set of elements contain a positive one?”. A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form “Whether a set of vertices induces an edge”. Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg n,(1+o(1))(nlg n),2n and 2n queries were proposed, respectively. In this paper we improve them to and n+lg n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements …