Tell a friend
Print
Gerzen, Tatjana (2011) On a group testing problem: Characterization of graphs with 2-complexity c_2 and maximum number of edges. Discrete Applied Mathematics. Elsevier. doi: 10.1016/j.dam.2011.06.026.
Full text not available from this repository.
Abstract
Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988): Suppose a graph G contains one defective edge e*. Find the endpoints of e* by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of e* or not. What is then the minimum number c_2 of tests, which are needed in the worst case to identify e*? This problem was partially solved by Gerzen (2009) by deriving sharp lower and upper bounds for c_2. In addition, it was proved that the determination of c_2 is an NP-complete problem. Among others, it was shown that an uper bound for the number of edges holds for graphs with 2-complexity c_2. In the present paper, we study the class of graphs for which this bound is sharp and characterize these graphs in several ways.
| Item URL in elib: | https://elib.dlr.de/70266/ | ||||||
|---|---|---|---|---|---|---|---|
| Document Type: | Article | ||||||
| Title: | On a group testing problem: Characterization of graphs with 2-complexity c_2 and maximum number of edges | ||||||
| Authors: |
| ||||||
| Date: | 30 July 2011 | ||||||
| Journal or Publication Title: | Discrete Applied Mathematics | ||||||
| Refereed publication: | Yes | ||||||
| Open Access: | No | ||||||
| Gold Open Access: | No | ||||||
| In SCOPUS: | Yes | ||||||
| In ISI Web of Science: | Yes | ||||||
| DOI: | 10.1016/j.dam.2011.06.026 | ||||||
| Publisher: | Elsevier | ||||||
| Status: | Published | ||||||
| Keywords: | Graph; Combinatorial search; Group testing problem | ||||||
| HGF - Research field: | Aeronautics, Space and Transport | ||||||
| HGF - Program: | Space | ||||||
| HGF - Program Themes: | Communication and Navigation | ||||||
| DLR - Research area: | Raumfahrt | ||||||
| DLR - Program: | R KN - Kommunikation und Navigation | ||||||
| DLR - Research theme (Project): | R - Vorhaben Ionosphäre (old) | ||||||
| Location: | Neustrelitz | ||||||
| Institutes and Institutions: | Institute of Communication and Navigation > Navigation | ||||||
| Deposited By: | Gerzen, Tatjana | ||||||
| Deposited On: | 31 Aug 2011 08:32 | ||||||
| Last Modified: | 06 Sep 2019 15:21 |
Repository Staff Only: item control page
