@techreport{TR-DCC-95-21,
  number = {DCC-95-21},
  author = {Meidanis, João and Munuera, Erasmo G.},
  title = {A Linear Time Algorithm for Binary Phylogeny using {PQ}-Trees},
  month = {December},
  year = {1995}, 
  institution = {Department of Computer Science, University of Campinas},
  note = {In English, 6 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      The Binary Phylogeny Problem is to reconstruct a tree reporting
      the evolutionary history of a group of taxa for which a binary
      matrix of characteristics is given.  Gusfield presented an
      $O(mn)$-time algorithm for this problem with $n$ taxa and $m$
      characteristics.  This bound is tight if the input is given as an
      $n\times m$ matrix.  In this paper we show that a linear time
      algorithm is possible provided the input is given as a list of the
      ``1'' positions in the matrix.  The PQ-trees introduced by Booth
      and Leuker are used here.  More precisely, we show that a binary
      phylogeny exists if and only if the input admits a PQ-tree without
      Q nodes.  This immediately gives a linear time algorithm for the
      problem.
  }
}