Supertree construction with constraint programming

I P Gent, P Prosser, B M Smith, W Wei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


A central goal of systematics is the construction of a tree of life, where the tree represents the relationship between all living things. The leaf nodes of the tree correspond to species and the internal nodes to hypothesized species, assumed to be extinct, where species have diverged. One problem that biologists face is to assemble a supertree from many smaller trees that have overlapping leaf sets. Polytime algorithms have been proposed for this problem [3,5]. We present a simple constraint encoding of this problem. This is based on the observation that any rooted tree can be considered as being min-ultrametric when we label interior nodes with their depth in that tree. That is, any path from the root to a leaf corresponds to a strictly increasing sequence. Our encoding takes a radically different approach to solving these problems, and represents a new perspective.
Original languageEnglish
Title of host publicationPrinciples and practice of constraint programming-CP 2003: 9th international conference, CP 2003, Kinsale, Ireland, September 29 -October 3, 2003: proceedings
EditorsF. Rossi
Number of pages5
ISBN (Print)978-3-540-20202-8
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743




Dive into the research topics of 'Supertree construction with constraint programming'. Together they form a unique fingerprint.

Cite this