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 | ||||||

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