標題: | A competitive algorithm in searching for many edges in a hypergraph |
作者: | Chen, Ting Hwang, Frank K. 應用數學系 Department of Applied Mathematics |
關鍵字: | competitive algorithm;hypergraph;edge-searching problem;group testing;graph searching |
公開日期: | 15-二月-2007 |
摘要: | 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. (c) 2006 Elsevier B.V. All rights reserved. |
URI: | http://dx.doi.org/10.1016/j.dam.2006.07.008 http://hdl.handle.net/11536/11129 |
ISSN: | 0166-218X |
DOI: | 10.1016/j.dam.2006.07.008 |
期刊: | DISCRETE APPLIED MATHEMATICS |
Volume: | 155 |
Issue: | 4 |
起始頁: | 566 |
結束頁: | 571 |
顯示於類別: | 期刊論文 |