Technical Report 2006-020

Combining Tree Partitioning, Precedence, Incomparability, and Degree Constraints, with an Application to Phylogenetic and Ordered-Path Problems

Nicolas Beldiceanu, Pierre Flener, and Xavier Lorca

April 2006

The tree and path constraints, for digraph partitioning by vertex disjoint trees and paths respectively, are unified within a single global constraint, including a uniform treatment of a variety of useful side constraints, such as precedence, incomparability, and degree constraints. The approach provides a sharp improvement over an existing path constraint, but can also efficiently handle tree problems, such as the phylogenetic supertree construction problem. The key point of the filtering is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints.

Available as PDF (740 kB, no cover)

Download BibTeX entry.