Hamid Kameli - Non-adaptive Group Testing on Graphs

dmtcs:1368 - Discrete Mathematics & Theoretical Computer Science, March 26, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-9
Non-adaptive Group Testing on GraphsArticle

Authors: Hamid Kameli

    Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problem of learning a hidden graph for some especial cases, such as hamiltonian cycle, cliques, stars, and matchings. This problem is motivated by problems in chemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, we consider a graph G and a subgraph H of G and we assume that G contains exactly one defective subgraph isomorphic to H. The goal is to find the defective subgraph by testing whether an induced subgraph contains an edge of the defective subgraph, with the minimum number of tests. We present an upper bound for the number of tests to find the defective subgraph by using the symmetric and high probability variation of Lovász Local Lemma.


    Volume: Vol. 20 no. 1
    Section: Combinatorics
    Published on: March 26, 2018
    Accepted on: January 25, 2018
    Submitted on: May 3, 2017
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Machine Learning

    Consultation statistics

    This page has been seen 567 times.
    This article's PDF has been downloaded 194 times.