Search problems on graphs (Q1082080): Difference between revisions
From MaRDI portal
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