Balanced randomized tree splitting with applications to evolutionary tree constructions

Ming Yang Kao, Andrzej Lingas, Anna Östlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on eficient construction of evolutionary trees: a new upper time-bound on the problem of constructing an evolutionary tree from experiments, and a relatively fast approximation algorithm for the maximum agreement subtree problem for binary trees for which the maximum number of leaves in an optimal solution is large. We also present new lower bounds for the problem of constructing an evolutionary tree from experiments and for the problem of constructing a tree from an ultrametric distance matrix.

Original languageEnglish (US)
Title of host publicationSTACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsChristoph Meinel, Sophie Tison
PublisherSpringer Verlag
Pages184-196
Number of pages13
ISBN (Print)354065691X, 9783540656913
DOIs
StatePublished - 1999
Event16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 - Trier, Germany
Duration: Mar 4 1999Mar 6 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1563
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999
CountryGermany
CityTrier
Period3/4/993/6/99

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Balanced randomized tree splitting with applications to evolutionary tree constructions'. Together they form a unique fingerprint.

  • Cite this

    Kao, M. Y., Lingas, A., & Östlin, A. (1999). Balanced randomized tree splitting with applications to evolutionary tree constructions. In C. Meinel, & S. Tison (Eds.), STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 184-196). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1563). Springer Verlag. https://doi.org/10.1007/3-540-49116-3_17