Title: A competitive algorithm to find all defective edges in a graph
Authors: Hwang, FK
Department of Applied Mathematics
Keywords: group testing;graph testing;competitive algorithm
Issue Date: 15-Jun-2005
Abstract: Consider a graph G (V, E) where a subset D E E is called the set of defective edges. The problem is to identify D with a small number of edge tests, where an edge test takes an arbitrary subset S and asks whether the subgraph G(S) induced by S intersects D (contains a defective edge). Recently, Johann gave an algorithm to find all d defective edges in a graph assuming d D I is known. We give an algorithm with d unknown which requires at most d([log(2) vertical bar E vertical bar] + 4) + 1 tests. The information-theoretic bound, knowing d, is about d log(2) (vertical bar E vertical bar/d). For d fixed, our algorithm is competitive with coefficient 1. (c) 2005 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2005.02.010
ISSN: 0166-218X
DOI: 10.1016/j.dam.2005.02.010
Volume: 148
Issue: 3
Begin Page: 273
End Page: 277
Appears in Collections:Articles

Files in This Item:

  1. 000230062600007.pdf