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

Fingerprint

Polynomial time
Polynomials
K-tree
Rooted Trees
Maximum Degree
Computing
Vertex of a graph

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

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

Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. / Ganapathysaravanabavan, Ganeshkumar; Warnow, Tandy.

Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. ed. / Bernard M. E. Moret; Olivier Gascuel. Springer-Verlag, 2001. p. 156-163 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2149).

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

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 BME Moret & O Gascuel (eds), Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2149, Springer-Verlag, pp. 156-163, 1st International Workshop on Algorithms in Bioinformatics, WABI 2001, Arhus, Denmark, 8/28/01. https://doi.org/10.1007/3-540-44696-6_12
Ganapathysaravanabavan G, Warnow T. Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In Moret BME, Gascuel O, editors, Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. Springer-Verlag. 2001. p. 156-163. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-44696-6_12
Ganapathysaravanabavan, Ganeshkumar ; Warnow, Tandy. / Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. editor / Bernard M. E. Moret ; Olivier Gascuel. Springer-Verlag, 2001. pp. 156-163 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{be4363fd4e124ef8b00bdb4ee136bf3d,
title = "Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time",
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.",
author = "Ganeshkumar Ganapathysaravanabavan and Tandy Warnow",
year = "2001",
month = "1",
day = "1",
doi = "10.1007/3-540-44696-6_12",
language = "English (US)",
isbn = "3540425160",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "156--163",
editor = "Moret, {Bernard M. E.} and Olivier Gascuel",
booktitle = "Algorithms in Bioinformatics - First International Workshop, WABI 2001 {\AA}rhus Denmark, August 28-31, 2001 Proceedings",

}

TY - GEN

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

AU - Ganapathysaravanabavan, Ganeshkumar

AU - Warnow, Tandy

PY - 2001/1/1

Y1 - 2001/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84959037630&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959037630&partnerID=8YFLogxK

U2 - 10.1007/3-540-44696-6_12

DO - 10.1007/3-540-44696-6_12

M3 - Conference contribution

AN - SCOPUS:84959037630

SN - 3540425160

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 156

EP - 163

BT - Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings

A2 - Moret, Bernard M. E.

A2 - Gascuel, Olivier

PB - Springer-Verlag

ER -