Finding a classification tree over a given set of elements that is compatible with a given family of classification trees over subsets of that set is a common problem in many application areas, such as the historical analysis of languages, the theory of relational databases, and phylogenetic supertree construction. We present a constraint programming approach to this problem. First, we introduce a natural and compact graph representation of a family of classification trees. Second, we provide a complete filtering algorithm for the classification tree problem, based on this normal form.
Available as PDF (170 kB, no cover)
Download BibTeX entry.