Reconstruction of hidden graphs and threshold group testing
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
281 | en_US |
dc.citation.issue |
2 | en_US |
dc.citation.spage |
270 | en_US |
dc.citation.volume |
22 | en_US |
dc.citation.woscount |
2 | |
dc.contributor.author |
Chang, Huilan | en_US |
dc.contributor.author |
Chen, Hong-Bin | en_US |
dc.contributor.author |
Fu, Hung-Lin | en_US |
dc.contributor.author |
Shi, Chie-Huai | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:29:22Z | |
dc.date.available |
2014-12-08T15:29:22Z | |
dc.date.issued |
2011-08-01 | en_US |
dc.description.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. | en_US |
dc.identifier.doi |
10.1007/s10878-010-9291-0 | en_US |
dc.identifier.issn |
1382-6905 | en_US |
dc.identifier.journal |
JOURNAL OF COMBINATORIAL OPTIMIZATION | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1007/s10878-010-9291-0 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/21149 | |
dc.identifier.wosnumber |
WOS:000292571000010 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Graph search | en_US |
dc.subject |
Threshold group testing | en_US |
dc.subject |
Pooling design | en_US |
dc.subject |
Adaptive algorithms | en_US |
dc.title |
Reconstruction of hidden graphs and threshold group testing | en_US |
dc.type |
Article | en_US |
檔案
- 000292571000010.pdf (501.7 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Chang, H., Chen, H.-B., Fu, H.-L., & Shi, C.-H. (2011). Reconstruction of hidden graphs and threshold group testing. JOURNAL OF COMBINATORIAL OPTIMIZATION, 22(2), 270–281. https://doi.org/10.1007/s10878-010-9291-0
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/21149