Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time

Ganeshkumar Ganapathysaravanabavan, Tandy Warnow

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

Abstract

In this paper, we consider the problem of computing a maximum compatible tree for k rooted trees when the maximum degree of all trees is bounded. We show that the problem can be solved in O(22kdnk) time, where n is the number of taxa in each tree, and every node in every tree has at most d children. Hence, a maximum compatible tree for k unrooted trees can be found in in O(22kdnk+1) time.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings
EditorsBernard M. E. Moret, Olivier Gascuel
PublisherSpringer-Verlag
Pages156-163
Number of pages8
ISBN (Print)3540425160
DOIs
StatePublished - Jan 1 2001
Externally publishedYes
Event1st International Workshop on Algorithms in Bioinformatics, WABI 2001 - Arhus, Denmark
Duration: Aug 28 2001Aug 31 2001

Publication series

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

Other

Other1st International Workshop on Algorithms in Bioinformatics, WABI 2001
CountryDenmark
CityArhus
Period8/28/018/31/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time'. Together they form a unique fingerprint.

  • Cite this

    Ganapathysaravanabavan, G., & Warnow, T. (2001). Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In B. M. E. Moret, & O. Gascuel (Eds.), Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings (pp. 156-163). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2149). Springer-Verlag. https://doi.org/10.1007/3-540-44696-6_12