Title of article
A revised algorithm for searching for all defective edges in a graph
Author/Authors
Ting Chen، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2011
Pages
3
From page
2266
To page
2268
Abstract
We consider the following generalization of the classical group testing problem. Given a graph image, which contains image defective edges, we want to identify all defective edges in image by testing whether an induced subgraph contains a defective edge or not. Recently, Hwang gave a competitive algorithm to identify all defective edges in a graph with image unknown. We will show an obvious mistake in the algorithm and propose a revised algorithm to solve the problem of searching for all defective edges in a graph.
Keywords
Competitive algorithm , Group testing , Graph testing
Journal title
Discrete Applied Mathematics
Serial Year
2011
Journal title
Discrete Applied Mathematics
Record number
887765
Link To Document