A search problem on graphs which generalizes some group testing problems with two defectives (Q1176719): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q789161 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Hartmut Schmeck / rank | |||
Normal rank |
Revision as of 03:18, 21 February 2024
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