A competitive algorithm in searching for many edges in a hypergraph
檔案
- 000244827700012.pdf (142.8 KB, Adobe PDF)
日期
2007-02-15
類型
系所
期刊名稱
DISCRETE APPLIED MATHEMATICS
卷期與頁次
第 155 卷第 4 期,頁 566–571
ISSN
0166-218X
語言
英文
摘要
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.