@inproceedings{cb086f9966e641708da84106c37c20c2,

title = "Inferring ordered trees from local constraints",

abstract = "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.",

author = "Leszek G{\c a}sieniec and Jansson, {Jesper Andreas} and Andrzej Lingas and Anna {\"O}stlin",

year = "1998",

language = "English",

volume = "20",

series = "Australian Computer Science Communications",

publisher = "Springer-Verlag Singapore Pte. Ltd.",

number = "3",

pages = "67--76",

booktitle = "Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98)",

note = "4th Australasian Theory Symposium, CATS 1998 ; Conference date: 02-02-1998 Through 03-02-1998",

}