Identifying defective network components through restricted group testing

被引：0
作者：
Ghosh, Diptesh [1 ]
机构：
[1] Indian Inst Management Ahmedabad, P&QM Area, Ahmadabad, Gujarat, India
来源：
OPSEARCH | 2019年 / 56卷 / 03期
关键词：
Switch networks; Node covering; Group testing; s-t Cuts; Heuristics; GRAPH;
D O I：
10.1007/s12597-019-00382-3
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we consider a network of switches in which some of the switches may malfunction. Our aim is to find out efficiently (a) if any of the switches in a network of switches are defective, and (b) if there are defective switches, to identify those switches. We find an optimal solution for the first problem and a heuristic solution to the second, and demonstrate the feasibility of our approach through computational experiments.
引用
收藏
页码：869 / 889
页数：21
相关论文
共 12 条
  • [1] [Anonymous], 1996, GENETIC MAPPING DNA
  • [2] Azwell T., 2011, MACONDO BLOWOUT ENV
  • [3] Adjacent Link Failure Localization With Monitoring Trails in All-Optical Mesh Networks
    Babarczi, Peter
    Janos Tapolcai
    Ho, Pin-Han
    [J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 2011, 19 (03) : 907 - 920
  • [4] Graph-Constrained Group Testing
    Cheraghchi, Mahdi
    Karbasi, Amin
    Mohajer, Soheil
    Saligrama, Venkatesh
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (01) : 248 - 262
  • [5] Du D.Z., 2000, COMBINATORIAL GROUP
  • [6] Dyachkov A., 1983, Problems Control Inf. Theory, V12, P229
  • [7] Hoshino E. A., 2011, ELECT NOTES DISCRETE, V37, P255
  • [8] Karbasi A, 2012, 2012 IEEE INFORMATION THEORY WORKSHOP (ITW), P292, DOI 10.1109/ITW.2012.6404678
  • [9] A SEQUENTIAL METHOD FOR SCREENING EXPERIMENTAL-VARIABLES
    LI, CH
    [J]. JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1962, 57 (298) : 455 - &
  • [10] MINIMAL CUT COVER OF A GRAPH WITH AN APPLICATION TO THE TESTING OF ELECTRONIC BOARDS
    LOULOU, R
    [J]. OPERATIONS RESEARCH LETTERS, 1992, 12 (05) : 301 - 305
12