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

Ganeshkumar Ganapathysaravanabavan; Tandy Warnow

doi: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

Ganeshkumar Ganapathysaravanabavan
, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceeding › Conference 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(2^2kdn^k) 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(2^2kdn^k+1) time.

Original language	English (US)
Title of host publication	Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings
Editors	Bernard M. E. Moret, Olivier Gascuel
Publisher	Springer
Pages	156-163
Number of pages	8
ISBN (Print)	3540425160
DOIs	https://doi.org/10.1007/3-540-44696-6_12
State	Published - 2001
Externally published	Yes
Event	1st International Workshop on Algorithms in Bioinformatics, WABI 2001 - Arhus, Denmark Duration: Aug 28 2001 → Aug 31 2001

Publication series

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

Other

Other	1st International Workshop on Algorithms in Bioinformatics, WABI 2001
Country/Territory	Denmark
City	Arhus
Period	8/28/01 → 8/31/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-44696-6_12

Library availability

Discover UIUC Full Text

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. 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, 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 proceeding › Conference 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, 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. 2001. p. 156-163. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 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, 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",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 1st International Workshop on Algorithms in Bioinformatics, WABI 2001 ; Conference date: 28-08-2001 Through 31-08-2001",

year = "2001",

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

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

address = "Germany",

}

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

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

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 - https://www.scopus.com/pages/publications/84959037630

UR - https://www.scopus.com/pages/publications/84959037630#tab=citedBy

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

T2 - 1st International Workshop on Algorithms in Bioinformatics, WABI 2001

Y2 - 28 August 2001 through 31 August 2001

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this