Geodesic
Non-adaptive Group Testing on Graphs
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1

Voir la notice de l'article provenant de la source Episciences

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\'asz Local Lemma. 
@article{DMTCS_2018_20_1_a10,
     author = {Kameli, Hamid},
     title = {Non-adaptive {Group} {Testing} on {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-9/}
}
TY  - JOUR
AU  - Kameli, Hamid
TI  - Non-adaptive Group Testing on Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-9/
DO  - 10.23638/DMTCS-20-1-9
LA  - en
ID  - DMTCS_2018_20_1_a10
ER  - 
%0 Journal Article
%A Kameli, Hamid
%T Non-adaptive Group Testing on Graphs
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-9/
%R 10.23638/DMTCS-20-1-9
%G en
%F DMTCS_2018_20_1_a10
Kameli, Hamid. Non-adaptive Group Testing on Graphs. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-9

Cité par Sources :