Inferring ordered trees from local constraints

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

Inferring ordered trees from local constraints

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

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-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 language	English
Title of host publication	Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98)
Pages	67-76
Volume	20
Publication status	Published - 1998
Event	4th Australasian Theory Symposium, CATS 1998 - Perth, Australia Duration: 2 Feb 1998 → 3 Feb 1998

Publication series

Name	Australian Computer Science Communications
Publisher	Springer-Verlag Singapore Pte. Ltd.
Number	3
Volume	20

Conference

Conference	4th Australasian Theory Symposium, CATS 1998
Country/Territory	Australia
City	Perth
Period	2/02/98 → 3/02/98

More information

https://dblp.uni-trier.de/db/conf/cats/cats1998.html

Cite this

@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",

}

Ga̧sieniec, L, Jansson, JA, Lingas, A & Östlin, A 1998, Inferring ordered trees from local constraints. in Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98). vol. 20, Australian Computer Science Communications, no. 3, vol. 20, pp. 67-76, 4th Australasian Theory Symposium, CATS 1998, Perth, Australia, 2/02/98. <https://dblp.uni-trier.de/db/conf/cats/cats1998.html>

Inferring ordered trees from local constraints. / Ga̧sieniec, Leszek; Jansson, Jesper Andreas; Lingas, Andrzej et al.
Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98). Vol. 20 1998. p. 67-76 (Australian Computer Science Communications; Vol. 20, No. 3).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Inferring ordered trees from local constraints

AU - Ga̧sieniec, Leszek

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

AU - Östlin, Anna

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

M3 - Conference article published in proceeding or book

VL - 20

T3 - Australian Computer Science Communications

SP - 67

EP - 76

BT - Proceedings of Fourth Computing: the Australasian Theory Symposium (CATS'98)

T2 - 4th Australasian Theory Symposium, CATS 1998

Y2 - 2 February 1998 through 3 February 1998

ER -

Inferring ordered trees from local constraints

Abstract

Publication series

Conference

More information

Fingerprint

Cite this