More efficient algorithms for searching for several edges in a hypergraph

The edge searching problem is a generalization of the classical group testing problem. Chen and Hwang studied the problem of searching for many edges in a hypergraph with rank r. They provided a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Recently, Hwang first gave a competitive algorithm to find all defective edges in a graph. Chen proposed a revised algorithm for the same problem requiring at most \(d \lceil \log _2 |E| \rceil + d^2 + 3d + 1\) $d\lceil {log}_2|E|\rceil +d^2+3d+1$ tests. In this paper, we will revisit the result proposed by Chen and give a more detailed analysis which implies that the revised algorithm actually requires at most \( d \lceil \log _2 |E| \rceil + 5d + 1\) $d\lceil {log}_2|E|\rceil +5d+1$ tests. Then we further study the edge searching problem in a hypergraph of rank r. Considering the special case of \(r=3\) $r=3$ , we will present more efficient algorithms to identify all defective edges in hypergraphs of rank 3.