A competitive algorithm in searching for many edges in a hypergraph |
| |
| Authors: | Ting Chen Frank K Hwang |
| |
| Institution: | a College of Statistics and Mathematics, Zhejiang Gongshang University, Hangzhou, PR China
b Department of Applied Mathematics, National Chiaotung University, Hsinchu, Taiwan, ROC 1 |
| |
| Abstract: | 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. |
| |
| Keywords: | Competitive algorithm Hypergraph Edge-searching problem Group testing Graph searching |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
