elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

An NP-Completeness Result of Edge Search in Graphs

Gerzen, Tatjana (2013) An NP-Completeness Result of Edge Search in Graphs. Graphs and Combinatorics. Springer. doi: 10.1007/s00373-013-1287-y. ISSN 0911-0119.

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

Kurzfassung

Consider the following generalization of the classical sequential group testing problem for two defective items: suppose a graph G contains n vertices two of which are defective and adjacent. Find the defective vertices by testing whether a subset of vertices of cardinality at most p contains at least one defective vertex or not. What is then the minimum number cp(G) of tests, which are needed in the worst case to find all defective vertices? In Gerzen (Discrete Math 309(20):5932–5942, 2009), this problem was partly solved by deriving lower and sharp upper bounds for cp(G). In the present paper we show that the computation of cp(G) is an NP-complete problem. In addition, we establish some results on cp(G) for random graphs.

elib-URL des Eintrags:https://elib.dlr.de/81811/
Dokumentart:Zeitschriftenbeitrag
Titel:An NP-Completeness Result of Edge Search in Graphs
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Gerzen, TatjanaTatjana.Gerzen (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:26 März 2013
Erschienen in:Graphs and Combinatorics
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
DOI:10.1007/s00373-013-1287-y
Verlag:Springer
ISSN:0911-0119
Status:veröffentlicht
Stichwörter:Graph Theory, NP Completeness, Search in Graph, Combinatorial Search
HGF - Forschungsbereich:Verkehr und Weltraum (alt)
HGF - Programm:Weltraum (alt)
HGF - Programmthema:W EO - Erdbeobachtung
DLR - Schwerpunkt:Weltraum
DLR - Forschungsgebiet:W EO - Erdbeobachtung
DLR - Teilgebiet (Projekt, Vorhaben):W - Vorhaben Ionosphärenerkundung (alt)
Standort: Neustrelitz
Institute & Einrichtungen:Institut für Kommunikation und Navigation > Navigation
Hinterlegt von: Gerzen, Tatjana
Hinterlegt am:18 Apr 2013 10:02
Letzte Änderung:07 Nov 2023 08:09

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.