Search problems on graphs (Q1082080)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Search problems on graphs
scientific article

    Statements

    Search problems on graphs (English)
    0 references
    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
    0 references
    search theory
    0 references
    group tests
    0 references
    complete graphs
    0 references
    bipartite graphs
    0 references