標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000244827700012.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。