A search problem on graphs which generalizes some group testing problems with two defectives
✍ Scribed by Thomas Andreae
- Publisher
- Elsevier Science
- Year
- 1991
- Tongue
- English
- Weight
- 499 KB
- Volume
- 88
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
A search problem on graphs which generalizes some group testing problems with two defectives, Discrete Mathematics 88 (1991) 121-127.
We consider a search problem which generalizes the group testing problems previously studied in papers of Chang/Hwang and Chang/Hwang/Lin.
In its general form for arbitrary graphs the problem was proposed by Aigner. Let G be a finite simple graph with vertex-set V(G) and edge-set E(G). Let e* E E(G) be an unknown edge. In order to find e* we choose a sequence of test-sets A c V(G) where after every test we are told whether or not e* is an edge of the subgraph induced by A. Find the minimum number c(G) of tests required. G is called P-optimal if c(G) achieves the usual information theoretic lower bound, i.e., c(G) = [log, IE(G)Il. It was shown by Chang and Hwang that all complete bipartite graphs are 2-optimal and Aigner observed that forests are 2-optimal. In the present paper we relate the parameter c(G) to the notion of a k-orderable graph. (We call G k-orderable if there exists a linear order vl, . . . , v, of the vertices of G such that each vi has at most k neighbors among IJ1,. . 3 vi_,; this is equivalent to saying that the well known coloring number of G introduced by ErdBs and Hajnal is at most k + 1.) Among other results we show that 2-orderable graphs are 2-optimal and provide upper bounds for c(G).