Title: Reconstruction of hidden graphs and threshold group testing
Authors: Chang, Huilan
Chen, Hong-Bin
Fu, Hung-Lin
Shi, Chie-Huai
應用數學系
Department of Applied Mathematics
Keywords: Graph search;Threshold group testing;Pooling design;Adaptive algorithms
Issue Date: 1-Aug-2011
Abstract: 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 (1 + 0(1))(nlgn), (1+0(1)) (nlgn/2), n + 2lgn 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 under a more general setting, in which there are two fixed thresholds l and u, with l <u, and the response to a query is positive if the tested subset of elements contains at least u positive elements, negative if it contains at most l positive elements, and it is arbitrarily given otherwise. For the threshold group testing problem with l=u-1, we show that p positive elements among n given elements can be determined by using O(plg n) queries, with a matching lower bound.
URI: http://dx.doi.org/10.1007/s10878-010-9291-0
http://hdl.handle.net/11536/21149
ISSN: 1382-6905
DOI: 10.1007/s10878-010-9291-0
Journal: JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume: 22
Issue: 2
Begin Page: 270
End Page: 281
Appears in Collections:Articles


Files in This Item:

  1. 000292571000010.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.