Uppsala University Department of Information Technology

Technical Report 2008-018

A Complete Characterisation of the Classification Tree Problem

Pierre Flener and Xavier Lorca

June 2008

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.

Uppsala Universitet