elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] 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.

Dieses Archiv kann nicht den Volltext zur Verfügung stellen.

Kurzfassung

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.

elib-URL des Eintrags:https://elib.dlr.de/70266/
Dokumentart:Zeitschriftenbeitrag
Titel:On a group testing problem: Characterization of graphs with 2-complexity c_2 and maximum number of edges
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Gerzen, Tatjanatatjana.gerzen (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:30 Juli 2011
Erschienen in:Discrete Applied Mathematics
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
DOI:10.1016/j.dam.2011.06.026
Verlag:Elsevier
Status:veröffentlicht
Stichwörter:Graph; Combinatorial search; Group testing problem
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Kommunikation und Navigation
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R KN - Kommunikation und Navigation
DLR - Teilgebiet (Projekt, Vorhaben):R - Vorhaben Ionosphäre (alt)
Standort: Neustrelitz
Institute & Einrichtungen:Institut für Kommunikation und Navigation > Navigation
Hinterlegt von: Gerzen, Tatjana
Hinterlegt am:31 Aug 2011 08:32
Letzte Änderung:06 Sep 2019 15:21

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.