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 :
بازگشت