Inferring ordered trees from local constraints

Leszek Ga̧sieniec, Jesper Andreas Jansson, Andrzej Lingas, Anna Östlin

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98)
Pages67-76
Volume20
Publication statusPublished - 1998
Event4th Australasian Theory Symposium, CATS 1998 - Perth, Australia
Duration: 2 Feb 19983 Feb 1998

Publication series

NameAustralian Computer Science Communications
PublisherSpringer-Verlag Singapore Pte. Ltd.
Number3
Volume20

Conference

Conference4th Australasian Theory Symposium, CATS 1998
Country/TerritoryAustralia
CityPerth
Period2/02/983/02/98

Cite this