A search problem on graphs which generalizes some group testing problems with two defectives (Q1176719): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Hartmut Schmeck / rank | |||
Property / reviewed by | |||
Property / reviewed by: Hartmut Schmeck / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3861131 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3050437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Search problems on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A ternary search problem on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Group Testing Problem on Two Disjoint Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Group testing with two defectives / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topology of series-parallel networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On chromatic number of graphs and set-systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Axioms and hulls / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: <i>k</i>-Degenerate Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4097334 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Über eine Eigenschaft der ebenen Komplexe / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:58, 15 May 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