Kaikoura tree theorems: Computing the maximum agreement subtree

Mike Steel, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {S1, S2,..., Sn} and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S0 of S such that P|S0 = Q|S0. This problem arises in evaluationary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n4.5 log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n2 + V) while the other has running time O(k2.5n2 log n + V). These algorithms also apply when the trees are constrained to be rooted; in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the searchproblem in the same running time as above.

Original languageEnglish (US)
Pages (from-to)77-82
Number of pages6
JournalInformation Processing Letters
Volume48
Issue number2
DOIs
StatePublished - Nov 8 1993
Externally publishedYes

Fingerprint

Computing
Theorem
Binary trees
Leaves
Binary Tree
Maximum Degree
Cardinality
Subset
Vertex of a graph

Keywords

  • Algorithms
  • Analysis of algorithms
  • Combinatorial problems

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this

Kaikoura tree theorems : Computing the maximum agreement subtree. / Steel, Mike; Warnow, Tandy.

In: Information Processing Letters, Vol. 48, No. 2, 08.11.1993, p. 77-82.

Research output: Contribution to journalArticle

@article{b7d281b8dda84c87a4341a9b36b17e94,
title = "Kaikoura tree theorems: Computing the maximum agreement subtree",
abstract = "The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {S1, S2,..., Sn} and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S0 of S such that P|S0 = Q|S0. This problem arises in evaluationary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n4.5 log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n2 + V) while the other has running time O(k2.5n2 log n + V). These algorithms also apply when the trees are constrained to be rooted; in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the searchproblem in the same running time as above.",
keywords = "Algorithms, Analysis of algorithms, Combinatorial problems",
author = "Mike Steel and Tandy Warnow",
year = "1993",
month = "11",
day = "8",
doi = "10.1016/0020-0190(93)90181-8",
language = "English (US)",
volume = "48",
pages = "77--82",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Kaikoura tree theorems

T2 - Computing the maximum agreement subtree

AU - Steel, Mike

AU - Warnow, Tandy

PY - 1993/11/8

Y1 - 1993/11/8

N2 - The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {S1, S2,..., Sn} and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S0 of S such that P|S0 = Q|S0. This problem arises in evaluationary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n4.5 log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n2 + V) while the other has running time O(k2.5n2 log n + V). These algorithms also apply when the trees are constrained to be rooted; in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the searchproblem in the same running time as above.

AB - The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {S1, S2,..., Sn} and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S0 of S such that P|S0 = Q|S0. This problem arises in evaluationary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n4.5 log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n2 + V) while the other has running time O(k2.5n2 log n + V). These algorithms also apply when the trees are constrained to be rooted; in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the searchproblem in the same running time as above.

KW - Algorithms

KW - Analysis of algorithms

KW - Combinatorial problems

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

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

U2 - 10.1016/0020-0190(93)90181-8

DO - 10.1016/0020-0190(93)90181-8

M3 - Article

AN - SCOPUS:0027912455

VL - 48

SP - 77

EP - 82

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -