A search problem on graphs which generalizes some group testing problems with two defectives (Q1176719)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A search problem on graphs which generalizes some group testing problems with two defectives |
scientific article |
Statements
A search problem on graphs which generalizes some group testing problems with two defectives (English)
0 references
25 June 1992
0 references
The author studies the problem of searching for an edge in a graph and tries to characterize classes of graphs with edges where \([\log_ 2 m]\) tests suffice to find an arbitrary edge. Graphs having this property are called 2-optimal. Among other results it is shown that graphs are 2- optimal, if they are 2-orderable, i.e. their vertices can be arranged in a sequence \(v_ 1,\dots,v_ n\) such that each \(v_ i\) has at most 2 direct neighbours among \(v_ 1,\dots,v_{i-1}\). Furthermore, several upper bounds are given for the maximum number of tests in a search.
0 references
searching
0 references
upper bounds
0 references