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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cheraghchi M, Karbasi A, Mohajer S, Saligrama V (2012) Graph-constrained group testing. IEEE Trans Inf Theory 58:248–262
Du DZ, Hwang FK (2006) Pooling designs and nonadaptive group testing: important tools for DNA sequencing, vol 18. Series on applied mathematics. World Scientific Publishing Co. Pte. Ltd., Hackensack
D’yachkov AG, Rykov VV (1982) Bounds for the length of disjunctive codes. Probl Inf Transm 18:7–13
Harvey NJ, Patrascu M, Wen Y, Yekhanin S, Chan VW (2007) Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs. In: Proceedings of the IEEE INFOCOM 2007—26th IEEE international conference on computer communications, pp 697–705
Karbasi A, Zadimoghaddam M (2012) Sequential group testing with graph constraints. In: 2012 IEEE information theory workshop, pp 292–296
Kautz W, Singleton R (1964) Nonrandom binary superimposed codes. IEEE Trans Inf Theory 10:363–377
Li CS, Ramaswami R (1997) Automatic fault detection, isolation, and recovery in transparent all-optical networks. J Lightwave Technol 15:1784–1793
Mas C, Tomkos I, Tonguz OK (2005) Failure location algorithm for transparent optical networks. IEEE J Sel Areas Commun 23:1508–1519
Tapolcai J, Ronyai L, Ho PH (2010) Optimal solutions for single fault localization in two dimensional lattice networks. In: 2010 Proceedings IEEE INFOCOM, pp 1–5
Ufimtsev V, Bhowmick S (2013) Application of group testing in identifying high betweenness centrality vertices in complex networks. In: Proceedings of eleventh workshop on mining and learning with graphs
Wen Y, Chan VWS, Zheng L (2005) Efficient fault-diagnosis algorithms for all-optical wdm networks with probabilistic link failures. J Lightwave Technol 23:3358–3371
Wu B, Yeung KL (2007) Monitoring cycle design for fast link failure detection in all-optical networks. In: IEEE GLOBECOM 2007—IEEE global telecommunications conference, pp 2315–2319
Zeng H, Huang C, Vukovic A (2006) A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles. Photonic Netw Commun 11:277–286
Acknowledgements
The authors express their gratitude to the two anonymous reviewers for their detailed and constructive comments which are very helpful to the improvement of the presentation of this paper. This research is supported in part by the JSPS Grant-in-Aid for Scientific Research (B) under Grant Nos. 18H01133 and 16H03118.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Luo, S., Matsuura, Y., Miao, Y. et al. Non-adaptive group testing on graphs with connectivity. J Comb Optim 38, 278–291 (2019). https://doi.org/10.1007/s10878-019-00379-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00379-0