We consider a problem of inferring an ordered tree from a set of local constraints on its leaves which we term as the ordered local consensus tree problem. Using our efficient decremental interval union algorithm, we show that the ordered local consensus tree problem for m constraints on n leaves can be deterministically solved in time O((m+n) log n): We also show that the related optimization problem of constructing an ordered local consensus tree for the maximum number of 3-leaf constraints is solvable in cubic time.
|Title of host publication
|Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98)
|Published - 1998
|4th Australasian Theory Symposium, CATS 1998 - Perth, Australia
Duration: 2 Feb 1998 → 3 Feb 1998
|Australian Computer Science Communications
|Springer-Verlag Singapore Pte. Ltd.
|4th Australasian Theory Symposium, CATS 1998
|2/02/98 → 3/02/98