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 (21)
Succinct representations of weighted trees supporting path queries ⋮ 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 ⋮ Tree Containment With Soft Polytomies ⋮ On finding the Adams consensus tree ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ On the extremal maximum agreement subtree problem ⋮ Efficient Algorithms for SNP Haplotype Block Selection Problems ⋮ Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract) ⋮ Maximum agreement and compatible supertrees ⋮ From constrained to unconstrained maximum agreement subtree in linear time ⋮ Computing the maximum agreement of phylogenetic networks ⋮ 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 algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ Faster algorithms for computing the R* consensus tree ⋮ Unnamed Item ⋮ Efficient computation of 2-medians in a tree network with positive/negative weights ⋮ An improved algorithm for the maximum agreement subtree problem ⋮ On the complexity of finding a largest common subtree of bounded degree ⋮ On the Maximum Agreement Subtree Conjecture for Balanced Trees
This page was built for publication: An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
