Search problems on graphs (Q1082080): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
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: Determination of a Subset from Certain Combinatorial Properties / 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: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5183260 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Determination of two vectors from the sum / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On \(B_ 2\)-sequences of vectors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4109144 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5550257 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Detection of Defective Members of Large Populations / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:21, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Search problems on graphs |
scientific article |
Statements
Search problems on graphs (English)
0 references
1986
0 references
The following search problem on graphs is studied: given a graph \(G=(V,E)\) and an unknown edge \(e\in E\), we can test whether a subset \(A\leq V\) contains both ends of e, one end, or neither. The edge e is to be located with the minimum number of tests. When G is a complete graph, this is a classical problem of finding ''defectives'' in a population when at most two defectives are present. Lower and upper bounds for the minimum number of tests are derived for complete graphs and for complete bipartite graphs. These give the exact values for \(K_{m,n}\), \(1\leq m\leq 4\).
0 references
search theory
0 references
group tests
0 references
complete graphs
0 references
bipartite graphs
0 references