@inproceedings{2333c3f5f1b24cf58bbc07061353ec49,
title = "On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees",
abstract = "This paper addresses the informational asymmetry for constructing an ultrametric evolutionary tree from upper and lower bounds on pairwise distances between n given species. We show that the tallest ultrametric tree exists and can be constructed in O(n2) time, while the existence of the shortest ultrametric tree depends on whether the lower bounds are ultrametric. The tallest tree construction algorithm gives a very simple solution to the construction of an ultrametric tree. We also provide an efficient O(n2)-time algorithm for checking the uniqueness of an ultrametric tree, and study a query problem for testing whether an ultrametric tree satisfies both upper and lower bounds.",
author = "Ting Chen and Kao, {Ming Yang}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 7th Annual European Symposium on Algorithms, ESA 1999 ; Conference date: 16-07-1999 Through 18-07-1999",
year = "1999",
doi = "10.1007/3-540-48481-7_22",
language = "English (US)",
isbn = "3540662510",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "248--256",
editor = "Jaroslav Ne{\v s}et{\v r}il",
booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",
}