A competitive algorithm in searching for many edges in a hypergraph

作者：Chen Ting; Hwang Frank K

来源：Discrete Applied Mathematics, 2007, 155(4): 566-571.

DOI：10.1016/j.dam.2006.07.008

• competitive algorithm
• hypergraph
• edge-searching problem
• group testing
• graph searching

We give a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Damaschke did the d = 1 case for 2-graphs, Triesch extended the d = 1 case to r-graphs, and Johann did the general d case for 2-graphs. So ours is the first attempt to solve the searching for defective edges problem in its full generality. Further, all the above three papers assumed d known. We give a competitive algorithm where d is unknown.

• 出版日期2007-2-15
• 单位浙江工商大学