Browsing by Author "Chen, Ting"

Now showing 1 - 1 of 1

A competitive algorithm in searching for many edges in a hypergraph
(2007-02-15)
Chen, Ting
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
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.