We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An NP-Completeness Result of Edge Search in Graphs.
- Authors
Gerzen, Tatjana
- 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 c( G) of tests, which are needed in the worst case to find all defective vertices? In Gerzen (Discrete Math 309(20):5932-5942, ), this problem was partly solved by deriving lower and sharp upper bounds for c( G). In the present paper we show that the computation of c( G) is an NP-complete problem. In addition, we establish some results on c( G) for random graphs.
- Subjects
COMPLETENESS theorem; GRAPH theory; GROUP testing; PROBLEM solving; RANDOM graphs; GENERALIZATION
- Publication
Graphs & Combinatorics, 2014, Vol 30, Issue 3, p661
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-013-1287-y