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