UNB/ CS/ David Bremner/ teaching/ cs6375/ examples/ scheduling

The ACM programming contest problem Color a tree turns out to be equivalent to scheduling with tree precedence constraints.

There is a fast solution to this first worked out (although not analyzed) by Horn in 1972.

I wanted to check my solution, so I modelled this as an integer program. Unlike Horn's algorithm, this takes no advantage of the special tree structure of the constraints. This is both good and bad: more general constraint DAGs can be modelled, but it is much slower to solve the integer program. Here some example data files, all trees