Constructing phylogenetic trees efficiently using compatibility criteria

Research output: Contribution to journalArticlepeer-review


The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two-state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990.

Original languageEnglish (US)
Pages (from-to)239-248
Number of pages10
JournalNew Zealand Journal of Botany
Issue number3
StatePublished - Jul 1 1993
Externally publishedYes


  • Algorithms
  • Evolution
  • Phylogenetic tree

ASJC Scopus subject areas

  • Ecology, Evolution, Behavior and Systematics
  • Plant Science


Dive into the research topics of 'Constructing phylogenetic trees efficiently using compatibility criteria'. Together they form a unique fingerprint.

Cite this