elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

On a group testing problem: Characterization of graphs with 2-complexity c_2 and maximum number of edges

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:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Gerzen, Tatjanatatjana.gerzen (at) dlr.deUNSPECIFIED
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

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.