• 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