Reconstruction of hidden graphs and threshold group testing

DOI10.1007/S10878-010-9291-0zbMath1232.05135OpenAlexW2047535013MaRDI QIDQ719032

Hong-Bin Chen, Hung-Lin Fu, Huilan Chang, Chie-Huai Shi

Publication date: 27 September 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9291-0

zbMATH Keywords

adaptive algorithmsgraph searchpooling designgraph reconstruction problemthreshold group testing problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (7)

Exact learning from an honest teacher that answers membership queries ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Learning a hidden graph ⋮ Threshold and Majority Group Testing ⋮ Group Testing with Multiple Mutually-Obscuring Positives ⋮ Non-adaptive Learning of a Hidden Hypergraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Nonadaptive algorithms for threshold group testing
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Sets pooling designs
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Threshold Group Testing
• On the interval containing at least one prime number
• Graph-Theoretic Concepts in Computer Science
• Optimal reconstruction of graphs under the additive model

This page was built for publication: Reconstruction of hidden graphs and threshold group testing