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