elib
DLR-Header
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.

Abstract

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
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Gerzen, Tatjanatatjana.gerzen (at) dlr.deUNSPECIFIED
Date:26 March 2013
Journal or Publication Title:Graphs and Combinatorics
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
DOI :[10.1007/s00373-013-1287-y]
Publisher:Springer
ISSN:0911-0119
Status:Published
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:18 Apr 2013 10:02

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.