• Title of article

    Recognizing DNA graphs is difficult Original Research Article

  • Author/Authors

    Rudi Pendavingh، نويسنده , , Petra Schuurman، نويسنده , , Gerhard J. Woeginger، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2003
  • Pages
    10
  • From page
    85
  • To page
    94
  • Abstract
    DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by Błażewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.
  • Keywords
    Computational complexity , Recognition algorithm , NP-hardness , Graph theory , DNA graphs , DNA computing , De Bruijn graph
  • Journal title
    Discrete Applied Mathematics
  • Serial Year
    2003
  • Journal title
    Discrete Applied Mathematics
  • Record number

    885527

    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=10&DC=885527