A revised algorithm for searching for all defective edges in a graph

作者：Chen, Ting^*

来源：Discrete Applied Mathematics, 2011, 159(18): 2266-2268.

DOI：10.1016/j.dam.2011.08.004

• Group testing
• Graph testing
• Competitive algorithm

We consider the following generalization of the classical group testing problem. Given a graph G = (V. E), which contains d defective edges, we want to identify all defective edges in G 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 d 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.

• 出版日期2011-12-6
• 单位浙江工商大学