DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] 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.

Full text not available from this repository.


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.

Item URL in elib:https://elib.dlr.de/81811/
Document Type:Article
Title:An NP-Completeness Result of Edge Search in Graphs
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Date:26 March 2013
Journal or Publication Title:Graphs and Combinatorics
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
Keywords:Graph Theory, NP Completeness, Search in Graph, Combinatorial Search
HGF - Research field:Aeronautics, Space and Transport (old)
HGF - Program:Space (old)
HGF - Program Themes:W EO - Erdbeobachtung
DLR - Research area:Space
DLR - Program:W EO - Erdbeobachtung
DLR - Research theme (Project):W - Vorhaben Ionosphärenerkundung (old)
Location: Neustrelitz
Institutes and Institutions:Institute of Communication and Navigation > Navigation
Deposited By: Gerzen, Tatjana
Deposited On:18 Apr 2013 10:02
Last Modified:07 Nov 2023 08:09

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.