Affordable Access

Access to the full text

Non-adaptive group testing on graphs with connectivity

Authors
  • Luo, Song1
  • Matsuura, Yuji1
  • Miao, Ying1
  • Shigeno, Maiko1
  • 1 University of Tsukuba, Graduate School of Systems and Information Engineering, Tsukuba, 305-8573, Japan , Tsukuba (Japan)
Type
Published Article
Journal
Journal of Combinatorial Optimization
Publisher
Springer-Verlag
Publication Date
Jan 16, 2019
Volume
38
Issue
1
Pages
278–291
Identifiers
DOI: 10.1007/s10878-019-00379-0
Source
Springer Nature
Keywords
License
Yellow

Abstract

Group testing refers to any procedure which groups arbitrary subsets of items into pools, and then tests each pool to identify the “sparse” defective items. This paper focuses on a probing scheme in non-adaptive group testing with graph-based constraints. Assume that all nodes function properly but there is at most one failed edge in an undirected graph. By sending probing signals in diagnosis process, we try to know if there is any edge failed, and if there is, to identify the failed edge. Each probing set is allowed only if the induced subgraph by the set is connected. The objective of this model is to identify the failed edge by the fewest possible probes. This paper gives a deterministic optimal probing scheme for complete graphs, and an essentially optimal probing scheme for torus grid graphs.

Report this publication

Statistics

Seen <100 times