A competitive algorithm to find all defective edges in a graph

被引:3
作者
Hwang, FK [1 ]
机构
[1] Natl Chiao Tung Univ, Dept Math Appl, Hsinchu, Taiwan
关键词
group testing; graph testing; competitive algorithm;
D O I
10.1016/j.dam.2005.02.010
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:273 / 277
页数:5
相关论文
共 6 条