...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Reconstruction of hidden graphs and threshold group testing
【24h】

Reconstruction of hidden graphs and threshold group testing

机译：重构隐藏图和阈值组测试

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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+o(1))(nlgn),(1+o(1))(fracnlgn2),n+2lgn(1+o(1))(nlg n),(1+o(1))(frac{nlg n}{2}),n+2lg n 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 ℓ and u, with ℓ
机译：经典的分组测试是一种搜索范例，其目标是通过询问以下形式的查询来识别大量元素中的单个积极元素：“一组元素是否包含一个积极元素？”。概括经典组测试问题的图重构问题是，通过询问以下形式的查询来从给定的图族中重构隐藏图：“一组顶点是否诱发边缘”。研究了哈密顿循环，匹配，星和团在n个顶点上的重构问题，并提出了分别使用最多2nlg n，（1 + o（1））（nlg n），2n和2n个查询的算法。在本文中，我们将它们改进为（1 + o（1））（nlgn），（1 + o（1））（fracnlgn2），n + 2lgn（1 + o（1））（nlg n），（1+ o（1））（frac {nlg n} {2}），n + 2lg n和n + lg n。阈值组测试是组测试的另一种概括，它是在更一般的设置下识别元素集合中的各个肯定元素，其中存在两个固定阈值ℓ和u，且ℓ

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号