An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
From MaRDI portal
Publication:2706115
DOI10.1137/S0097539796313477zbMath0976.68081MaRDI QIDQ2706115
Martín Farach-Colton, Mikkel Thorup, Ramesh Hariharan, Richard John Cole, Teresa M. Przytycka
Publication date: 19 March 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
Unnamed Item, On the Maximum Agreement Subtree Conjecture for Balanced Trees, Tree Containment With Soft Polytomies, Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract), Efficient computation of 2-medians in a tree network with positive/negative weights, Improved algorithms for maximum agreement and compatible supertrees, Faster algorithms for computing the R* consensus tree, An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees, Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, New common ancestor problems in trees and directed acyclic graphs, An improved algorithm for the maximum agreement subtree problem, Computing the maximum agreement of phylogenetic networks, On the extremal maximum agreement subtree problem, On the complexity of finding a largest common subtree of bounded degree, Succinct representations of weighted trees supporting path queries, On finding the Adams consensus tree, Maximum agreement and compatible supertrees, From constrained to unconstrained maximum agreement subtree in linear time, An algebraic view of the relation between largest common subtrees and smallest common supertrees, Efficient Algorithms for SNP Haplotype Block Selection Problems